#include <bits/stdc++.h>
using namespace std;

int main() 
{
  int t;
  cin >> t;
  while(t--)
  {
    int n;
    cin >> n;
    vector <int> a(n + 1);
    vector <int> lowest;
    vector <int> highest;
    vector <int> freq(n+1,-1);
    set <int> s,s2;
    set <int> :: iterator it;
    for (int i = 0; i < n; i++)
    {
      cin >> a[i];
      freq[a[i]] = 1;
    }
    for (int i = 1; i <= n; i++)
    {
      if (freq[i] == -1)
      {
        s.insert(i);
        s2.insert(i);
      }
    }
    for (int i = 0; i < n; i++)
    {
      if (a[i] == a[i - 1])
      {
        it =  s.lower_bound(a[i]);
        highest.push_back(*--it);
        s.erase(*it);
        it = s2.begin();
        cout << *it << " ";
        s2.erase(it);
      }
      else
      {
        cout << a[i] << " ";
        highest.push_back(a[i]);
      }
    }
    cout << endl;
    for (int i = 0; i < n; i++)
      cout << highest[i] << " ";
    cout << endl;
  }
}