#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <map>;
#include <set>;
#include <algorithm>

using namespace std;

int main()
{
    int t;
    cin >> t;
    int n;
    for(int i = 0; i < t; i++)
    {
        cin >> n;
        int mise[n];
        int pos[n];
        memset(pos, 0, sizeof(pos));
        map<int, int> T;
        set<int> comp;
        priority_queue<int, vector<int>, greater<int> > L;

        for(int i = 0; i < n; i++)
        {
            cin >> mise[i];
            if(T[mise[i]] == 0)
            {
                pos[i] = mise[i];
            }
            T[mise[i]] = 1;
            comp.insert(i + 1);
        }
        for(int i = 1; i <= n; i++)
        {
            if(T[i] == 0)
            {
                L.push(i);
            }
        }

        for(int i = 0; i < n; i++)
        {
            if(pos[i] == 0)
            {
                pos[i] = L.top();
                L.pop();
            }
        }

        for(int i = 0; i < n; i++)
        {
            if(i == 0)
            {
                cout << pos[i];
            }
            else
            {
                cout << " " << pos[i];
            }
        }
        cout << "\n";
        int pre;

        for(int i = 0; i < n; i++)
        {
            if(T[pos[i]] == 1)
            {
                pre = pos[i];
                comp.erase(pos[i]);
                continue;
            }
            else
            {
                pos[i] = *(--comp.upper_bound(pre));
                comp.erase(pos[i]);
            }
        }
        for(int i = 0; i < n; i++)
        {
            if(i == 0)
            {
                cout << pos[i];
            }
            else
            {
                cout << " " << pos[i];
            }
        }
        cout << "\n";
    }
    return 0;
}
