#include<bits/stdc++.h>
using namespace std;
#define all(a) begin(a), end(a)
#define sz(a) int(size(a))
#define rep(i,a,b) for(int i=a;i<(b);++i)
using vi = vector<int>;

const int MAXB = 7;
vector<vi> dranges[MAXB+1];

void gen(vi &a, vi &used, int idx, int n) {
    if(idx == n) {
        dranges[n].push_back(a);
        return;
    }
    for(int i = 0; i < n; i++) if(i != idx and !used[i]) {
        used[i] = true;
        a[idx] = i;
        gen(a, used, idx+1, n);
        a[idx] = -1;
        used[i] = false;
    }
}

void precomp() {
    srand(time(0));
    for(int n = 1; n <= MAXB; n++) {
        vi a(n, -1), used(n);
        gen(a, used, 0, n);
    }
}

void solve(int tc) {
    int N; cin >> N;
    vi A(N), pos(N);
    for(int i = 0; i < N; i++)
        cin >> A[i], --A[i], pos[A[i]] = i;

    vi finP, pPos(N), Q(N);

    if(N <= MAXB) {
        for(vi &P : dranges[N]) {
            rep(i,0,N) pPos[P[i]] = i;
            bool bad = false;
            rep(i,0,N) if((Q[i] = pPos[pos[i]]) == i) { bad = true; break; }
            if(bad) continue;
            finP = P;
            break;
        }
    } else {
        vi P(N); iota(all(P), 0);
        while(true) {
            random_shuffle(all(P));
            rep(i,0,N) pPos[P[i]] = i;
            bool bad = false;
            rep(i,0,N) if((Q[i] = pPos[pos[i]]) == i) { bad = true; break; }
            if(bad) continue;
            break;
        }
        finP = P;
    }

    if(sz(finP)) {
        // we got 'em
        cout << "Possible" << '\n';
        vi P = finP;
        for(int x : P) cout << ++x << ' ';
        cout << '\n';
        for(int x : Q) cout << ++x << ' ';
        cout << '\n';
        return;
    } else
        cout << "Impossible" << '\n';
}

int main() {
    cin.tie(0)->sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    precomp();
    int t = 1;
    cin >> t;
    for(int i = 1; i <= t; i++) solve(i);
    cout.flush(); return 0;
}