Amazing Trick

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 the cards in a row. Let the number on the $i$-th card from the left be $a_i$.

Then Alice selects two permutations $p$ and $q$. There is a restriction on $p$ and $q$: 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 $i$-th card from the left becomes the card $a[p[q[i]]$. The trick is considered successful if, after shuffling, the number on the $i$-th card from the left is $i$.

Help Alice choose the permutations $p$ and $q$, or determine if it is impossible for the given starting permutation $a$.

Input

The first line contains the number of test cases $t(1\le t\le 10^5)$.

Each test is described in two lines. The first line contains one integer $n(1\le n\le 10^5)$ — the number of cards. The second line contains $n$ 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 $n$ over all tests does not exceed $10^5$.

Output

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 $p$ and $q$.

Examples