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:
from collections import Counter as C,defaultdict as D,deque as Q
from operator import itemgetter as I
from itertools import product as P
from bisect import bisect_left as BL,bisect_right as BR
from heapq import heappush as HPUSH,heappop as HPOP
from math import floor as MF,ceil as MC, gcd as MG,factorial as F,sqrt as SQRT, inf as INFINITY,log as LOG
from sys import stdin, stdout
INPUT=stdin.readline
PRINT=stdout.write

def player1():
	print("")

def player2():
	print("")

def isPrime(n):

	for i in range(2,MC(SQRT(n))+1):
		if n%i==0:
			return False
	return True

def factors(x):

	ans=[]

	for i in range(1,MC(SQRT(x))+1):
		if x%i==0:
			ans.append(i)
			if x%(x//i)==0:
				ans.append(x//i)
	return ans


def main():


	for _ in range(int(INPUT())):

		n=int(INPUT());b=list(map(int,INPUT().split( )))

		c=C(b)
		if c[2*n]:
			PRINT("%d "%(-1))
			continue
		a=[i for i in range(1,2*n+1) if c[i]==0]
		ans=[];l=len(a)
		for v in b:

			index=BR(a,v)
			if index==l:
				ans=-1
				break
			ans.append(a[index])
			a.remove(a[index])
			l-=1
		else:
			for x,y in zip(b,ans):
				PRINT("%d %d "%(x,y))
			continue
		PRINT("%d "%(-1))






main()