#include<bits/stdc++.h>
using namespace std;

int main()
{
	int t;
	cin>>t;
	while(t--){
		long long n;
		cin>>n;
		long long a[n];
		map<long long,long long>m;
		vector<long long> vi,vx;
		set<long long>v;
		for(int i=0;i<n;i++)
		{
			cin>>a[i];
			m[a[i]]++;
		}
		for(long long i=1;i<=n;i++)
		{
			if(m[i]==0)
				v.insert(i);

		}
		set<long long > v2;
		v2=v;
		
		for(int i=0;i<n;i++)
		{
			int p;
			if(i==0){
			vi.push_back(a[i]);
			vx.push_back(a[i]);
			p=a[i];
			}
			if(a[i]!=a[i-1])
			{
				vi.push_back(a[i]);
				vx.push_back(a[i]);
				p=a[i];
			}
			if(a[i]==a[i-1])
			{
				p=a[i];
				set<long long>::iterator lower, upper,it;
				it=v.begin();
				vi.push_back(*it);
				v.erase(it);
				//set<long long>::iterator lower, upper;
				lower = v2.lower_bound(p);
				lower--;
				vx.push_back(*lower);
				v2.erase(lower);
				//cout<<*it<<" "<<*lower<<endl;

			}

		}

		 for (auto it = vi.begin()+1; it != vi.end(); it++)
        cout << *it << " ";
		cout<<endl;
	 for (auto it = vx.begin()+1; it != vx.end(); it++)
        cout << *it << " ";
		cout<<endl;

	}
return 0;
}