#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <iterator>
#define forn(i,n) for(int i = 0; i < n; i++)
#define pb push_back
#define ul unsigned long
#define ll long long
#define ull unsigned long long

using namespace std;


void solve() {
	int n;
	cin >> n;
	vector<int> q(n), res1(n), res2(n);
	forn(i, n) {
		int qi;
		cin >> qi;
		q[i] = res1[i] = res2[i] = qi;
	}

	set<int> left;
	vector<int> need_replace;
	for (int i = 1; i < n; i++) {
		if (q[i] == q[i - 1]) {
			res1[i] = res2[i] = -1;
		}
	}

	for (int i = 1; i <= (int)q.size(); i++) {
		left.insert(i);
	}

	forn(i, res1.size()) {
		if (res1[i] != -1) {
			left.erase(res1[i]);
		}
		else {
			need_replace.pb(i);
		}
	}

	//Min permutation
	int i = 0;
	for (auto it = left.begin(); it != left.end(); it++) {
		res1[need_replace[i]] = *it;
		i++;
	}
	//Max permutation
	for (int j = 0; j < need_replace.size(); j++) {
		auto it = --left.lower_bound(q[need_replace[j]]);
		res2[need_replace[j]] = *it;
		left.erase(it);
	}
	forn(i, n) cout << res1[i] << " ";
	cout << "\n";
	forn(i, n) cout << res2[i] << " ";
	cout << "\n";
	
}



int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	int t;
	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}