#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);
	int T; cin >> T;
	while (T--) {
		int n; cin >> n;
		vector<int> a(n);
		for (int i = 0; i < n; i++) {
			cin >> a[i];
			--a[i];
		}
		int cyc[3] = {};
		vector<bool> vis(n);
		for (int i = 0; i < n; i++) {
			if (vis[i]) continue;
			int cnt = 0;
			for (int v = i; !vis[v]; v = a[v]) {
				vis[v] = true;
				++cnt;
			}
			cyc[min(2, cnt - 1)]++;
		}
		vector<int> p(n), q(n);
		if (n == 1) {
			cout << "Impossible\n";
			continue;
		}
		else if (n == 2) {
			if (a[0] == 1 && a[1] == 0) {
				cout << "Impossible\n";
				continue;
			}
			else {
				p[0] = 1;
				p[1] = 0;
				q[0] = 1;
				q[1] = 0;
			}
		}
		else if (n == 3) {
			if (cyc[0] == 1 && cyc[1] == 1) {
				cout << "Impossible\n";
				continue;
			}
			else if (cyc[0] == 3) {
				p[0] = 1;
				p[1] = 2;
				p[2] = 0;
			}
			else {
				p[0] = a[0];
				p[1] = a[1];
				p[2] = a[2];
			}
		}
		else {
			vector<int> w;
			fill(vis.begin(), vis.end(), false);
			for (int i = 0; i < n; i++) {
				if (vis[i]) continue;
				for (int v = i; !vis[v]; v = a[v]) {
					vis[v] = true;
					w.push_back(v);
				}
			}
			for (int i = 0; i < n; i++) {
				p[w[i]] = w[(i + n - 2) % n];
			}
		}
		for (int i = 0; i < n; i++) {
			q[a[p[i]]] = i;
		}
		cout << "Possible\n";
		for (int i = 0; i < n; i++) {
			assert(i != p[i]);
			assert(i != q[i]);
		}
		for (int i = 0; i < n; i++) cout << p[i] + 1 << ' '; cout << '\n';
		for (int i = 0; i < n; i++) cout << q[i] + 1 << ' '; cout << '\n';
	}
}