```go
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
)

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var t int
	fmt.Fscan(in, &t)
	for test := 0; test < t; test++ {
		var n int
		fmt.Fscan(in, &n)
		a := make([]int, n+1)
		for i := 1; i <= n; i++ {
			fmt.Fscan(in, &a[i])
		}
		b := make([]int, n+1)
		for i := 1; i <= n; i++ {
			b[a[i]] = i
		}

		// Count number of 2-cycles
		var k int
		visited := make([]bool, n+1)
		for i := 1; i <= n; i++ {
			if !visited[i] {
				length := 0
				curr := i
				for !visited[curr] {
					visited[curr] = true
					curr = b[curr]
					length++
				}
				if length == 2 {
					k++
				}
			}
		}

		if n == 1 || (n <= 3 && k == 1) {
			fmt.Fprintln(out, "Impossible")
			continue
		}

		// Now construct
		visited2 := make([]bool, n+1)
		q := make([]int, n+1)
		for i := 1; i <= n; i++ {
			if !visited2[i] {
				var cycle []int
				curr := i
				for !visited2[curr] {
					visited2[curr] = true
					cycle = append(cycle, curr)
					curr = b[curr]
				}
				l := len(cycle)
				if l >= 3 {
					for j := 0; j < l; j++ {
						q[cycle[j]] = cycle[(j-1+l)%l]
					}
				}
			}
		}

		// Collect remaining
		var rem []int
		for i := 1; i <= n; i++ {
			if q[i] == 0 {
				rem = append(rem, i)
			}
		}
		s := len(rem)
		if s > 0 {
			sort.Ints(rem)
			idx := make(map[int]int)
			for ii := 0; ii < s; ii++ {
				idx[rem[ii]] = ii
			}
			badarr := make([]bool, s)
			for ii := 0; ii < s; ii++ {
				p := rem[ii]
				if b[p] != p {
					badd := (idx[b[p]] - ii + s) % s
					badarr[badd] = true
				}
			}
			var chosend int
			for d := 1; d < s; d++ {
				if !badarr[d] {
					chosend = d
					break
				}
			}
			// Set q
			for ii := 0; ii < s; ii++ {
				targetidx := (ii + chosend) % s
				q[rem[ii]] = rem[targetidx]
			}
		}

		// Compute q_inv
		qinv := make([]int, n+1)
		for i := 1; i <= n; i++ {
			qinv[q[i]] = i
		}

		// Compute p
		p := make([]int, n+1)
		for i := 1; i <= n; i++ {
			p[i] = b[qinv[i]]
		}

		// Output
		fmt.Fprintln(out, "Possible")
		for i := 1; i <= n; i++ {
			fmt.Fprintf(out, "%d ", p[i])
		}
		fmt.Fprintln(out)
		for i := 1; i <= n; i++ {
			fmt.Fprintf(out, "%d ", q[i])
		}
		fmt.Fprintln(out)
	}
}
```