#include<bits/stdc++.h>

#define f first
#define s second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) x.begin(),x.end()

using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());


void test(){
    int n;
    scanf("%i",&n);
    vector<int> a(n);
    vector<int> pos(n);
    for(int i=0;i<n;i++){
        scanf("%i",&a[i]);
        a[i]--;
        pos[a[i]]=i;
    }
    vector<int> perm(n);
    iota(all(perm),0);
    int bound=0;
    if(n<=3)bound=100;
    else bound=1e9;
    for(int i=0;i<bound;i++){
        shuffle(all(perm),rng);
        bool ok=1;
        for(int i=0;i<n;i++){
            if(perm[i]!=a[i]&&perm[i]!=i){

            }
            else{
                ok=0;
                break;
            }
        }
        if(!ok)continue;
        printf("Possible\n");
        vector<int> pos2(n);
        for(int i=0;i<n;i++){
            pos2[perm[i]]=i;
        }
        for(int i=0;i<n;i++){
            printf("%i ",pos[perm[i]]+1);
        }
        printf("\n");
        for(int i=0;i<n;i++){
            printf("%i ",pos2[i]+1);
        }
        printf("\n");
        return;
    }
    printf("Impossible\n");
}
int main(){
    int t;
    scanf("%i",&t);
    while(t--){
        test();
    }
}