#include<bits/stdc++.h> 
using namespace std;
namespace Sakurajima_Mai{
    #define ms(a) memset(a,0,sizeof(a))
    #define repi(i,a,b) for(int i=a,bbb=b;i<=bbb;++i)//attention reg int or reg ll ?
    #define repd(i,a,b) for(int i=a,bbb=b;i>=bbb;--i)
    #define reps(s) for(int i=head[s],v=e[i].to;i;i=e[i].nxt,v=e[i].to)
    #define ce(i,r) i==r?'\n':' '
    #define pb push_back 
    #define all(x) x.begin(),x.end()
    #define gmn(a,b) a=min(a,b)
    #define gmx(a,b) a=max(a,b)
    #define fi first
    #define se second                         
    typedef long long ll;
    typedef unsigned long long ull;
    typedef double db;
    const int infi=1e9;//infi较大，注意涉及inf相加时爆int
    const ll infl=4e18;
    inline ll ceil_div(ll a,ll b){ return (a+b-1)/b; }
    inline ll pos_mod(ll a,ll b){ return (a%b+b)%b; }
    //std::mt19937 rnd(time(0));//std::mt19937_64 rnd(time(0));
}
using namespace Sakurajima_Mai;
namespace Fast_Read{
    inline int qi(){
        int f=0,fu=1; char c=getchar();
        while(c<'0'||c>'9'){ if(c=='-')fu=-1; c=getchar(); }
        while(c>='0'&&c<='9'){ f=(f<<3)+(f<<1)+c-48; c=getchar(); }
        return f*fu;
    }
    inline ll ql(){
        ll f=0;int fu=1; char c=getchar();
        while(c<'0'||c>'9'){ if(c=='-')fu=-1; c=getchar(); }
        while(c>='0'&&c<='9'){ f=(f<<3)+(f<<1)+c-48; c=getchar(); }
        return f*fu;
    }
    inline db qd(){
        char c=getchar();int flag=1;double ans=0;
        while((!(c>='0'&&c<='9'))&&c!='-') c=getchar();
        if(c=='-') flag=-1,c=getchar();
        while(c>='0'&&c<='9') ans=ans*10+(c^48),c=getchar();
        if(c=='.'){c=getchar();for(int Bit=10;c>='0'&&c<='9';Bit=(Bit<<3)+(Bit<<1)) ans+=(double)(c^48)*1.0/Bit,c=getchar();}
        return ans*flag;
    }
}
namespace Read{
    #define si(a) scanf("%d",&a)
    #define sl(a) scanf("%lld",&a)
    #define sd(a) scanf("%lf",&a)
    #define ss(a) scanf("%s",a)
    #define rai(x,a,b) repi(i,a,b) x[i]=qi()
    #define ral(x,a,b) repi(i,a,b) x[i]=ql()
}
namespace Out{
    #define pi(x) printf("%d",x)
    #define pl(x) printf("%lld",x)
    #define ps(x) printf("%s",x)
    #define pc(x) printf("%c",x)
    #define pe() puts("")
}
namespace DeBug{
    #define MARK false
    #define DB if(MARK) 
    #define pr(x) cout<<#x<<": "<<x<<endl
    #define pra(x,a,b) cout<<#x<<": "<<endl; \
            repi(i,a,b) cout<<x[i]<<" ";     \
            puts("");   
    #define FR(a) freopen(a,"r",stdin)
    #define FO(a) freopen(a,"w",stdout)
}
using namespace Fast_Read;
using namespace Read;
using namespace Out;
using namespace DeBug;
const int MAX_N=2e5+5;
int n,q[MAX_N];
int ans[MAX_N];
set<int> s;
void solve_min()
{
	repi(i,1,n) s.insert(i);
	ans[1]=q[1],s.erase(q[1]);
	repi(i,2,n){
		if(q[i]==q[i-1]) ans[i]=*s.begin();
		else ans[i]=q[i];
		s.erase(ans[i]);
	}
	repi(i,1,n) pi(ans[i]),pc(' ');
	pe();
}
void solve_max()
{
	ans[1]=q[1];
	repi(i,1,q[1]-1) s.insert(i);
	int last=q[1];
	repi(i,2,n){
		if(q[i]==q[i-1]) ans[i]=*s.rbegin(),s.erase(ans[i]);
		else{
			ans[i]=q[i];
			repd(j,q[i]-1,last+1) s.insert(j);
			last=q[i];
		}
	}
	repi(i,1,n) pi(ans[i]),pc(' ');
	pe();
}
int main()
{
	int T=qi();
	while(T--)
	{
		n=qi();
		rai(q,1,n);
		solve_min(),solve_max();
	}
    return 0;
}