Alice is a magician and she creates a new trick. She has n cards with different numbers from 1 to n written on them. First, she asks an audience member to shuffle the deck and put cards in a row. Let’s say the i-th card from the left has the number ai on it.
Then Alice picks two permutations p and q. There is a restriction on p and q — permutations can’t have fixed points. Which means ∀i:pi=i and qi=i.
After permutations are chosen, Alice shuffles the cards according to them. Now the i-th card from the left is the card a[p[q[i]]. The trick is considered successful if i-th card from the left has the number i on it after the shuffles.
Help Alice pick the permutations p and q or say it is not possible for the specific starting permutation a.
The first line contains the number of tests t (1≤t≤105).
Each test is described in two lines. The first line contains one integer n (1≤n≤105) — the number of cards. The second line contains n integers ai (1≤ai≤n,∀i=j:ai=aj) — the initial permutation of the cards.
It is guaranteed that the sum of n over all tests does not exceed 105.
Print the answer for each test case in the same order the cases appear in the input.
For each test case, print “Impossible” in a single line, if no solution exists.
Otherwise, print "Possible" in the first line, and in the following two lines print permutations p and q.