Problem: A permutation is a sequence of n integers from 1 to n, in which all numbers occur exactly once. For example, [1], [3, 5, 2, 1, 4], [1, 3, 2] are permutations, and [2, 3, 2], [4, 3, 1], [0] are not.

Polycarp was presented with a permutation p of numbers from 1 to n. However, when Polycarp came home, he noticed that in his pocket, the permutation p had turned into an array q according to the following rule: 

  * q_i = max(p_1, p_2, …, p_i). 



Now Polycarp wondered what lexicographically minimal and lexicographically maximal permutations could be presented to him.

An array a of length n is lexicographically smaller than an array b of length n if there is an index i (1 ≤ i ≤ n) such that the first i-1 elements of arrays a and b are the same, and the i-th element of the array a is less than the i-th element of the array b. For example, the array a=[1, 3, 2, 3] is lexicographically smaller than the array b=[1, 3, 4, 2].

For example, if n=7 and p=[3, 2, 4, 1, 7, 5, 6], then q=[3, 3, 4, 4, 7, 7, 7] and the following permutations could have been as p initially: 

  * [3, 1, 4, 2, 7, 5, 6] (lexicographically minimal permutation); 
  * [3, 1, 4, 2, 7, 6, 5]; 
  * [3, 2, 4, 1, 7, 5, 6]; 
  * [3, 2, 4, 1, 7, 6, 5] (lexicographically maximum permutation). 



For a given array q, find the lexicographically minimal and lexicographically maximal permutations that could have been originally presented to Polycarp.

Input

The first line contains one integer t (1 ≤ t ≤ 10^4). Then t test cases follow.

The first line of each test case contains one integer n (1 ≤ n ≤ 2 ⋅ 10^5).

The second line of each test case contains n integers q_1, q_2, …, q_n (1 ≤ q_i ≤ n).

It is guaranteed that the array q was obtained by applying the rule from the statement to some permutation p.

It is guaranteed that the sum of n over all test cases does not exceed 2 ⋅ 10^5.

Output

For each test case, output two lines: 

  * on the first line output n integers — lexicographically minimal permutation that could have been originally presented to Polycarp; 
  * on the second line print n integers — lexicographically maximal permutation that could have been originally presented to Polycarp; 

Example

Input


4
7
3 3 4 4 7 7 7
4
1 2 3 4
7
3 4 5 5 5 7 7
1
1


Output


3 1 4 2 7 5 6 
3 2 4 1 7 6 5 
1 2 3 4 
1 2 3 4 
3 4 5 1 2 7 6 
3 4 5 2 1 7 6 
1 
1 

Solution (in PYTHON3):

Solution:
''' ===============================
    -- @uthor : Kaleab Asfaw
    -- Handle : Kaleab_Asfaw
    -- Bio    : High-School Student
    ==============================='''

# Fast IO
import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0
    def __init__(self, file): self._fd = file.fileno(); self.buffer = BytesIO(); self.writable = "x" in file.mode or "r" not in file.mode; self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b: break
            ptr = self.buffer.tell(); self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0; return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE)); self.newlines = b.count(b"\n") + (not b); ptr = self.buffer.tell(); self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1; return self.buffer.readline()
    def flush(self):
        if self.writable: os.write(self._fd, self.buffer.getvalue()); self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
    def __init__(self, file): self.buffer = FastIO(file); self.flush = self.buffer.flush; self.writable = self.buffer.writable; self.write = lambda s: self.buffer.write(s.encode("ascii")); self.read = lambda: self.buffer.read().decode("ascii"); self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout); input = lambda: sys.stdin.readline().rstrip("\r\n")
# Others
# from math import floor, ceil, gcd
# from decimal import Decimal as d
mod = 10**9+7
def lcm(x, y): return (x * y) / (gcd(x, y))
def fact(x, mod=mod):
    ans = 1
    for i in range(1, x+1): ans = (ans * i) % mod
    return ans
def arr2D(n, m, default=0): return [[default for j in range(m)] for i in range(n)]
def arr3D(n, m, r, default=0): return [[[default for k in range(r)] for j in range(m)] for i in range(n)]
def sortDictV(x): return {k: v for k, v in sorted(x.items(), key = lambda item : item[1])}
class DSU:
    def __init__(self, length): self.length = length; self.parent = [-1] * self.length  # O(log(n))
    def getParent(self, node, start):  # O(log(n))
        if node >= self.length: return False
        if self.parent[node] < 0:
            if start != node: self.parent[start] = node
            return node
        return self.getParent(self.parent[node], start)
    def union(self, node1, node2):  # O(log(n))
        parent1 = self.getParent(node1, node1); parent2 = self.getParent(node2, node2)
        if parent1 == parent2: return False
        elif self.parent[parent1] <= self.parent[parent2]: self.parent[parent1] += self.parent[parent2]; self.parent[parent2] = parent1
        else: self.parent[parent2] += self.parent[parent1]; self.parent[parent1] = parent2
        return True
    def getCount(self, node):  return -self.parent[self.getParent(node, node)] # O(log(n))

def exact(num):
    if abs(num - round(num)) <= 10**(-9):return round(num)
    return num

def minn(n, lst):
    vis = [0] * (n+3)
    
    for i in lst:
        vis[i] = 1

    val = -1
    cur = [0] * (n+2)
    
    lst1 = sorted(list(set(lst)))
    lst1 = [0] + lst1
    for i in range(len(lst1)-1):
        if lst1[i] != lst1[i+1] - 1:
            val = lst1[i] + 1
            break

    ans = []
    for i in lst:
        if cur[i] == 0:
            cur[i] = 1
            ans.append(i)
        else:
            ans.append(val)
            val += 1
            while vis[val] == 1:
                val += 1
    return ans

def maxx(n, lst):
    vis = [0] * (n+3)
    for i in lst:
        vis[i] = 1

    nxt = {}
    for i in range(1, n+1):
        nxt[i] = i-1

    ans = []
    cur = [0] * (n+2)

    for i in lst:
        if cur[i] == 0:
            cur[i] = 1
            ans.append(i)
        else:
            val = i - 1
            val1 = val
            while vis[val] == 1:
                val = nxt[val]
            nxt[val1] = val-1 
            ans.append(val)
            vis[val] = 1
    return ans
    
def p(lst):
    for i in lst:
        print(i, end=" ")
    print()
    
def solve(n, lst):
    p(minn(n, lst))
    p(maxx(n, lst))


for _ in range(int(input())): # Multicase
    n = int(input())
    lst = list(map(int, input().split()))
    solve(n, lst)