#pragma ide diagnostic ignored "misc-no-recursion"

#include "bits/stdc++.h"

using namespace std;
typedef long long ll;
typedef long double db;

#define TESTCASE 1

static constexpr int MOD = 998'244'353;
static constexpr int MAX_N = 1 << 19;
static constexpr int INF = 1e9;

static void solve([[maybe_unused]] int tc) {
    int N;
    cin >> N;

    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        A[i]--;
    }
    vector<int> B = A;

    auto solve = [&](int l, int r) {
        sort(B.begin() + l, B.begin() + r);
        do {
            bool ok = true;
            for (int i = l; i < r; i++) {
                ok = ok && B[i] != A[i] && B[i] != i;
            }
            if (ok) return true;
        } while (next_permutation(B.begin() + l, B.begin() + r));
        return false;
    };

    int i;
    for (i = 0; i + 8 <= N; i++) {
        assert (solve(i, i + 4));
    }
    if (solve(i, N)) {
        cout << "Possible\n";

        vector<int> P(N), Q(N);
        for (int i = 0; i < N; i++) {
            P[B[i]] = i;
            Q[A[i]] = B[i];
        }
        for (int i = 0; i < N; i++) {
            cout << P[i] + 1 << " \n"[i + 1 == N];
        }
        for (int i = 0; i < N; i++) {
            cout << Q[i] + 1 << " \n"[i + 1 == N];
        }
    } else {
        cout << "Impossible\n";
    }
}

int main() {
    ios::sync_with_stdio(false);

    if (const char *f = getenv("REDIRECT_STDOUT"); f) {
        freopen(f, "w", stdout);
    }

    int T = 1;
#if TESTCASE
    cin >> T;
#endif

    for (int t = 1; t <= T; t++) {
        solve(t);
    }

    return 0;
}