#include <bits/stdc++.h>
using namespace std ;
 
#define ll              long long  
#define ld              long double
#define pll             pair<ll,ll>
#define pb              push_back
#define all(v)          begin(v), end(v)
#define sz(a)           (ll)a.size()
#define F               first
#define S               second
#define INF             2000000000000000000
#define endl            "\n"
#define mem0(x)         memset(x, 0, sizeof(x))
#define mem1(x)         memset(x, -1, sizeof(x))
#define rep(i,k,n)      for (ll i = k; i <= n; ++i) 
#define repr(i,k,n)     for (ll i = k; i >= n; --i)
#define br              cout<<"\n";
 
template<typename T, typename U> static inline void amin(T &x, U y) {if (y < x) x = y;} 
template<typename T, typename U> static inline void amax(T &x, U y) {if (x < y) x = y;}
 
template <typename T> void read(T &p){cin >> p;}
template <typename T, typename T1> void read(pair<T, T1> &p){read(p.F);read(p.S);}
template <typename T> void read(T arr[], ll n){for (ll i = 0; i < n; i++) read(arr[i]);}
template <typename T> void read(vector<T> &arr){for (ll i = 0; i < arr.size(); i++)read(arr[i]);}
 
template <typename T> void print(T &n){cout << n;} 
template <typename T, typename T1>void print(pair<T, T1> &p){print(p.F);cout<<" ";print(p.S);}
template <typename T>void print(T arr[], ll n){for (ll i = 0; i < n; i++){print(arr[i]);cout<< " ";}}
template <typename T>void print(vector<T> &arr){for (ll i = 0; i < arr.size(); i++){print(arr[i]);cout<<" ";}}
template <typename T>void print(set<T> &arr){for (auto i : arr){ print(i); cout<< " ";}}
template <typename T>void print(multiset<T> &arr){for (auto i : arr){print(i);cout<< " ";}}
template <typename T, typename T1> void print(map<T, T1> &m){for (auto i : m){print(i.F);cout<<" -> ";print(i.S); br;}}
 
void solve(){
    
    ll n;
    cin>>n; 

    ll mn[n], mx[n], u[n+1], u1[n+1], p1 = 1, ar[n]; 
    mem0(u); 
    mem0(u1);
    mem0(mx);  
    set<ll> st; 

    rep(i, 0, n-1){
    	cin>>ar[i]; 
    	ll t = ar[i];

    	if(u[t]){
    		while(u[p1])
    			p1++; 
    		mn[i] = p1; 
    		p1++; 
    	}else{
    		mn[i] = t; 
    		mx[i] = t; 
    		u[t]++;
    		u1[t]++;  
    	}

    	st.insert(-(i+1)); 
    }


    rep(i, 0, n-1){
    	if(mx[i]){
    		// ll t = mx[i]-1; 
    		// i++; 
			auto it = st.find(-mx[i]);
			vector<ll> del;
			del.pb(-mx[i]);
			it++; 

			// cout<<"MX[i] = "<<mx[i]<<" i = "<<i<<endl;
			i++;
			for(auto t = it; it != st.end() and mx[i]==0; it++){
				mx[i] = -(*it);
				del.pb(*it);
				i++;
			}

			for(auto x: del){
				// cout<<x<<" "; 
				st.erase(st.find(x)); 
			}
    		
    		i--; 
    	}


    }

    print(mn, n); 
    br;
    print(mx, n); 
    br;
}
 
 
int main()
{ 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 
    int test = 1; 
    cin>>test;
    while(test--){
        solve(); 
    }
 
    return 0; 
}
