#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
#define vi vector<int>
#define ii pair<int,int>
#define vii vector<ii>
#define si set<int>
#define msi map<string,int>
#define pb push_back
#define fi first
#define se second

#define sp " "

#pragma GCC optimize("Ofast")  
#pragma GCC target("avx,avx2,fma") 

const int inf = 0x3f3f3f3f;
const int MX = 5e5+5;
const int mxl = 105;
const int mod = 1e9+7;

int main(){
	int tc; cin>>tc;
	for(int ntc=1;ntc<=tc;ntc++){
		int n; cin>>n;
		int arr[n+1],ans[n+1],mx[n+1];
		arr[0]=0; memset(ans,0,sizeof(ans)); memset(mx,0,sizeof(mx));
		for(int i=1;i<=n;i++)
			cin>>arr[i];
		set<int>s1,s2;
		int mncnt=1;
		for(int i=1;i<=n;i++){
			if(arr[i]!=arr[i-1]){
				ans[i]=arr[i];
				s1.insert(ans[i]);
			}
		}
		for(int i=1;i<=n;i++){
			if(ans[i]==0){
				while(s1.count(mncnt))
					mncnt++;
				ans[i]=mncnt;
				s1.insert(ans[i]);
			}
		}
		int mxcnt=n;
		set<int>rem;
		for(int i=1;i<=n;i++)
			rem.insert(i);
		for(int i=1;i<=n;i++){
			if(arr[i]!=arr[i-1]){
				mx[i]=arr[i];
				rem.erase(arr[i]);
			}
		}
		for(int i=1;i<=n;i++){
			if(mx[i]!=0)mxcnt=mx[i];
			else if(mx[i]==0){
				auto idx=--rem.lower_bound(mxcnt);
				mx[i]=*idx;
				rem.erase(idx);
			}
		}
		for(int i=1;i<=n;i++)
			cout<<ans[i]<<sp;
		cout<<"\n";
		for(int i=1;i<=n;i++)
			cout<<mx[i]<<sp;
		cout<<"\n";
	}
}