Amazing Trick#11320
Alice is a magician, and she creates a new trick. She has cards with different numbers from to written on them. First, she asks an audience member to shuffle the deck and put the cards in a row. Let the number on the -th card from the left be a_i.
Then Alice selects two permutations and . There is a restriction on and : permutations can't have fixed points. In other words, \forall i: p_i \ne i and q_i \ne i.
Once permutations are chosen, Alice shuffles the cards according to them. Now the -th card from the left becomes the card a[p[q[i]]]. The trick is considered successful if, after shuffling, the number on the -th card from the left is .
Help Alice choose the permutations and , or determine if it is impossible for the given starting permutation .
The first line contains the number of test cases (1 \le t \le 10^5).
Each test is described in two lines. The first line contains one integer (1 \le n \le 10^5) — the number of cards. The second line contains integers a_i (1 \le a_i \le n, \forall i \ne j: a_i \ne a_j) — the initial permutation of the cards.
It is guaranteed that the sum of over all tests does not exceed 10^5.
Print the answer for each test case in the order they appear in the input.
For each test case, print "Impossible" on a single line if no solution exists.
Otherwise, print "Possible" on the first line, followed by two lines containing the permutations and .
Example 1