// set vim: fdm=marker sw=4 ts=4 et

#define _CRT_DISABLE_PERFCRIT_LOCKS
#include <bits/stdc++.h>

using namespace std;

typedef int_fast64_t ll;
// const ll modulo = 1000000007;

#ifndef countof
#define countof(x) (sizeof(x) / sizeof(*(x)))
#endif

// --------------------------------------------------------------------------------

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    size_t T;
    cin >> T;
    for (size_t t = 0; t < T; ++t) {
        int n;
        cin >> n;

        vector<ll> q;
        q.reserve(n);
        copy_n(istream_iterator<ll>(cin), n, back_inserter(q));

        vector<ll> p_min, p_max;
        p_min.reserve(n);
        p_max.reserve(n);

        set<ll> min_avail;
        set<ll, std::greater<ll>> max_avail;
        for (ll i = 1; i <= n; ++i) {
            min_avail.insert(i);
            max_avail.insert(i);
        }

        ll i = 0;
        while (i < n) {
            ll j = i;
            while (j < n && q[j] == q[i]) {
                ++j;
            }

            p_min.push_back(q[i]);
            min_avail.erase(q[i]);
            auto it_min = min_avail.begin();

            auto it_max = max_avail.find(q[i]);
            p_max.push_back(*it_max);
            it_max = max_avail.erase(it_max);

            for (ll k = 0; k < j - i - 1; ++k) {
                p_min.push_back(*it_min);
                it_min = min_avail.erase(it_min);

                p_max.push_back(*it_max);
                it_max = max_avail.erase(it_max);
            }

            i = j;
        }

        copy(begin(p_min), end(p_min), ostream_iterator<ll>(cout, " "));
        cout << endl;
        copy(begin(p_max), end(p_max), ostream_iterator<ll>(cout, " "));
        cout << endl;
    }
    return 0;
}

// --------------------------------------------------------------------------------

