#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fast_io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define all(v) v.begin(),v.end()

const int mod = 1e9 + 7;
vector<int> getMin (int res[], set<int> s, int n) {
    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        if (res[i]) {
            v[i] = res[i];
        }
        else {
            v[i] = *s.begin();
            s.erase(s.begin());
        }
    }
    return v;
}

vector<int> getMax (int res[], int a[], set<int> s, int n) {
    int sufMin[n];
    sufMin[n - 1] = n;
    for (int i = n - 2; i >= 0; i--) {
        if (res[i] != 0) {
            sufMin[i] = min(sufMin[i + 1], res[i]);
        }
        else sufMin[i] = sufMin[i + 1];
    }
    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        if (res[i] == 0) {
            auto it = s.lower_bound(sufMin[i]);
            while (it == s.end() || (*it > sufMin[i] || *it > a[i])) {
                it--;
            }
            v[i] = *it;
            s.erase(v[i]);
        }
        else v[i] = res[i];
    }
    return v;
}
int main (){
    fast_io;
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int a[n];
        for (int i = 0; i < n; i++)
            cin >> a[i];
        int res[n];
        set<int> s;
        for (int i = 1; i <= n; i++)
            s.insert(i);
        memset(res, 0, sizeof(res));
        res[0] = a[0];
        s.erase(a[0]);
        for (int i = 1; i < n; i++) {
            if (a[i] != a[i - 1]) {
                res[i] = a[i];
                s.erase(a[i]);
            }
        }
        vector<int> mini = getMin(res, s, n);
        vector<int> maxi = getMax(res, a, s, n);
        for (auto it: mini)
            cout << it << ' ';
        cout << endl;
        for (auto it: maxi)
            cout << it << ' ';
        cout << endl;
    }
}
