//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx,avx2,sse,sse2")
#include <bits/stdc++.h>
using namespace std;
#define rep(i, j, n) for (ll i = j; i <= n; i++)
#define per(i, j, n) for (ll i = j; i >= n; i--)
#define ll long long
#define ld long double
#define vi vector<ll>
constexpr ll mod = 1e9 + 7;

ll t = 1;
ll n;

void solve() {
  // Code goes here
  cin >> n;
  vi q(n);
  rep(i, 0, n - 1) cin >> q[i];
  ll minm = 1;
  vi lmin, lmax;
  set<ll> done;
  done.insert(q[0]);
  lmin.push_back(q[0]);
  rep(i, 1, n - 1) {
    if (q[i] == q[i - 1]) {
      while (done.count(minm))
        ++minm;
      lmin.push_back(minm);
      done.insert(minm);
    } else {
      lmin.push_back(q[i]);
      done.insert(q[i]);
    }
  }
  done.clear();
  rep(i, 0, n - 1) done.insert(i + 1);
  done.erase(q[0]);
  lmax.push_back(q[0]);
  rep(i, 1, n - 1) {
    if (q[i] == q[i - 1]) {
      ll cur = q[i] - 1;
      auto it = done.upper_bound(q[i]);
      --it;
      lmax.push_back(*it);
      done.erase(it);
    } else {
      lmax.push_back(q[i]);
      done.erase(q[i]);
    }
  }
  rep(i, 0, n - 1) cout << lmin[i] << ' ';
  cout << '\n';
  rep(i, 0, n - 1) cout << lmax[i] << ' ';
  cout << '\n';
}

int main() {
  ios::sync_with_stdio(false);
  cin >> t;
  rep(i, 1, t) {
    // cout<<"Case #" << i << ": ";
    solve();
  }
}