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 PYTHON):

Solution:
from collections import defaultdict as dd, Counter, OrderedDict as od, deque
from itertools import combinations as comb, permutations as perm
from functools import reduce
from math import log, ceil, floor
from fractions import gcd

import os, sys

#sys.stdin = open("pc.txt", "r")
raw_input = sys.stdin.readline

int_input = lambda : int(raw_input())
list_input = lambda : list(raw_input().strip())
explode_input = lambda sep :raw_input().split(sep)
format_input = lambda object : map(object, raw_input().split())


t = int_input()

for t_itr in xrange(t):
	n = int_input()
	b = format_input(int)

	ans = []
	used = Counter(b)

	for n_itr in xrange(n):
		x, y = b[n_itr], b[n_itr] + 1

		if used.get(x, -1) != -1:
			used[x] -= 1
			if used[x] < 1:
				used.pop(x)

			for x_itr in xrange(x, 2 * n + 1):
				if used.get(x_itr, -1) == -1:
					ans.append(x_itr)
					used[x_itr] = 1
					y = x_itr + 1
					break 

			for y_itr in xrange(y, 2 * n + 1):
				if used.get(y_itr, -1) == -1:
					ans.append(y_itr)
					used[y_itr] = 1
					break

	m = len(ans)
	t = m != 2 * n

	for x in ans:
		if x > 2 * n:
			t = 1
			break

	if t == 1:
		print "-1"
	else:
		print " ".join(map(str, ans))