Problem: You are given a sequence b_1, b_2, …, b_n. Find the lexicographically minimal permutation a_1, a_2, …, a_{2n} such that b_i = min(a_{2i-1}, a_{2i}), or determine that it is impossible.

Input

Each test contains one or more test cases. The first line contains the number of test cases t (1 ≤ t ≤ 100).

The first line of each test case consists of one integer n — the number of elements in the sequence b (1 ≤ n ≤ 100).

The second line of each test case consists of n different integers b_1, …, b_n — elements of the sequence b (1 ≤ b_i ≤ 2n).

It is guaranteed that the sum of n by all test cases doesn't exceed 100.

Output

For each test case, if there is no appropriate permutation, print one number -1.

Otherwise, print 2n integers a_1, …, a_{2n} — required lexicographically minimal permutation of numbers from 1 to 2n.

Example

Input


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


Output


1 2 
-1
4 5 1 2 3 6 
-1
1 3 5 6 7 9 2 4 8 10 

Solution (in PYTHON3):

Solution:
def bubbleSort(arr): 
    n = len(arr) 
  
    # Traverse through all array elements 
    for i in range(n): 
  
        # Last i elements are already in place 
        for j in range(0, n-i-1): 
  
            # traverse the array from 0 to n-i-1 
            # Swap if the element found is greater 
            # than the next element 
            if arr[j] < arr[j+1] : 
                arr[j], arr[j+1] = arr[j+1], arr[j] 
number_of_testcase=int(input())
for i in range(number_of_testcase):
    n=int(input())
    numbers_list=list(map(int,input().split(' ')))
    initial_list=numbers_list.copy()
    #available_numbers=list(set(range(1,2*n+1))-set(initial_list))
    available_numbers=[x for x in list(range(1,2*n+1)) if x not in initial_list]
    #print(available_numbers)
    flag2=1
    final_dict={}   
    for i in initial_list:
        flag=0
        for j in available_numbers:
            if(i<j):
                flag=1
                final_dict[i]=j
                available_numbers.remove(j)
                break
        if(flag==0):
            print('-1')
            flag2=0
            break
    if(flag2==1):
        for j in initial_list:
            print(str(j)+' '+str(final_dict[j]),end=' ')
        print('')