#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<ll ,ll> pll;
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define all(X) (X).begin(), (X).end()
#define REP(i,x,y) for(ll i = x;i <= y;++i)
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
vector<string> vec_splitter(string s) {
    for(char& c: s) c = c == ','?  ' ': c;
    stringstream ss; ss << s;
    vector<string> res;
    for(string z; ss >> z; res.push_back(z))
        ;
    return res;
}
void debug_out(vector<string> args, int idx) { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, Head H, Tail... T) {
    if(idx > 0) cerr << ", ";
    stringstream ss; ss << H;
    cerr << args[idx] << " = " << ss.str();
    debug_out(args, idx + 1, T...);
}
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __VA_ARGS__)
void localTest() {
    #ifndef ONLINE_JUDGE
        freopen("inp", "r", stdin);
        freopen("out", "w", stdout);
    #endif      
}
void solver() {
    ll n;
    cin >> n;
    vector<ll> A(n);
    set<ll> st, tmp;
    for(ll i = 1; i <= n; ++i) {
        st.insert(i);
    }
    for(auto &x : A) {
        cin >> x;
        if(st.find(x) != st.end()) {
            st.erase(x);
        }
    }   
    tmp = st;
    cout << A[0] << " ";
    for(ll i = 1; i < n; ++i) {
        if(A[i] == A[i - 1]) {
            cout << *st.begin() << " ";
            st.erase(*st.begin());
        } else {
            cout << A[i] << " ";
        }
    }
    cout << "\n";
    st = tmp;
    cout << A[0] << " ";
    for(ll i = 1; i < n; ++i) {
        if(A[i] == A[i - 1]) {
            auto lo = st.lower_bound(A[i]);
            --lo;
            cout << *lo << " ";
            st.erase(*lo);
        } else {
            cout << A[i] << " ";
        }
    }
    cout << "\n";

}
int main() {

    localTest();
    fastio;
    ll t;
    cin >> t;
    while(t--) {
        solver();
    }

    return 0;
}