#include <bits/stdc++.h>

using namespace std;

inline void printArr(const int* a, int n) {
    cout << a[0];
    for(int i = 1; i < n; i++) {
        cout << " " << a[i];
    }
    cout << '\n';
}

void solve1(const int* q, int n) {
    bool vis[n];
    memset(vis, false, sizeof vis);

    int a[n]; a[0] = q[0];
    vis[q[0]-1] = true;

    int pre = q[0], p = 0;
    for(int i = 1; i < n; i++) {
        if(q[i] == pre) {
            while(p < n && vis[p]) p++;
            a[i] = p+1;
            vis[p] = true;
        }
        else {
            a[i] = q[i];
            vis[q[i]-1] = true;
            pre = q[i];
        }
    }

    printArr(a, n);
}

void solve2(const int* q, int n) {
    list<int> li;
    for(int i = n; i > 0; i--)
        li.emplace_back(i);

    typedef list<int>::iterator Iter;
    Iter its[n]; int k = n-1;
    for(auto iter = li.begin(); iter != li.end(); iter++) {
        its[k--] = iter;
    }

    int a[n]; a[0] = q[0];
    auto it = li.erase(its[q[0]-1]);
    int pre = q[0];
    for(int i = 1; i < n; i++) {
        if(q[i] == pre) {
            a[i] = *it;
            it = li.erase(it);
        }
        else {
            a[i] = q[i];
            pre = q[i];
            it = li.erase(its[q[i]-1]);
        }
    }

    printArr(a, n);
}

int main() {
    int t; cin >> t;
    while(t--) {
        int n; cin >> n;
        int q[n];
        for(int& x: q) cin >> x;

        solve1(q, n);
        solve2(q, n);
    }

    return 0;
}
