#include <bits/stdc++.h>

using namespace std;

// Theorem: I

typedef long long ll;

int main(){
 ios::sync_with_stdio(0);cin.tie(0);
 int  t; cin >> t;
 while(t > 0){
 	t--;
 	int n; cin >> n;
 	vector<int> arr(n);for(int i = 0; i < n; i++)cin >> arr[i];
 	// for minimal choose smallest smaller than max
 	// for maximal choose largest smaller than max
 	set<int> st;for(int i = 1; i <= n; i++)st.insert(i);
 	st.erase(arr[0]);
 	cout << arr[0] << " ";
 	for(int i = 1; i < n; i++){
 		if(arr[i] == arr[i - 1]){
 			cout << *st.begin() << " ";
 			st.erase(*st.begin());
 		}else{
 			cout << arr[i] << " " ;
 			st.erase(arr[i]);
 		}
 	}
 	cout << endl;
		for(int i = 1; i <= n; i++)st.insert(-1 * i);
		st.erase(-1 * arr[0]);
		cout << arr[0] << " ";
		for(int i = 1; i < n; i++){
			if(arr[i] != arr[i - 1]){
				cout << arr[i] << " ";
				st.erase(-1 * arr[i]);
			}else{
				cout << -1 * *st.lower_bound(-1 * arr[i]) << " ";
				st.erase(*st.lower_bound(-1 * arr[i]));
			}
		}
		cout << endl;
	}

}
