#include <iostream>
#include <vector>
#include <map>
#include <cmath>
#include <string>
#include <set>
#include <unordered_set>
#include <algorithm>
#include <unordered_map>
using namespace std;

#define lli long long int
#define ll long long
#define sp ' '
#define nl '\n'
#define push push_back
#define pop pop_back
#define make make_pair
#define forn(i,j,k) for (ll i = j; i <= k; ++i)
#define rev_for(i,j,k) for(ll i = j;i >= k; i--)
#define for_(i,n) for(ll i=0;i < n; i++)
#define r_for(i,n) for(ll i=n-1;i >= 0; i--)
#define inc_for(i,j,k,l) for (ll i = j; i <= k; i+=l)
#define dcr_for(i,j,k,l) for (ll i = j; i >= k; i-=l)
//TODO:check the constraint lli or int
//becasuse i always.....
void test_cases(){
	int n;
	cin>>n;
	set<int> c;
	vector<int> min(n),in,max(n);
	forn(i,1,n){
		c.insert(i);
		min[i-1]=0;
	}
	vector<int> a(n);
	int p=0;
	for_(i,n){
		cin>>a[i];
		if(a[i]!=p){
			p=a[i];
			c.erase(p);
			min[i]=p;
			max[i]=p;
		}else{
			in.push(i);
		}
	}
	int m=0;
	for (std::set<int>::iterator i = c.begin(); i != c.end(); ++i)
	{
		min[in[m]]=*i;
		m++;
	}
	m=0;
	for_(i,in.size()){
		std::set<int>::iterator result =c.upper_bound(a[in[i]]);
		--result;
    	a[in[i]]=*result;
    	c.erase(*result);
	}
	for_(i,n){
		cout<<min[i]<<sp;
	}
	cout<<nl; 
	for_(i,n){
		cout<<a[i]<<sp;
	}
}
int main(int argc, char const *argv[])
{
	int n=1;
	cin>>n;
	forn(i,1,n){
		// cout<<"Case #"<<i<<": ";
		test_cases();
		cout<<nl;
	}
	return 0;
}