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

Solution:
import java.util.*;
import java.awt.print.Book;
import java.io.*;
import java.math.BigInteger;

public class A {
	static long mod = (long) (1e9 + 7);

	public static long facn(long n, long x) {
		long ans = 1;
		for (int i = 1; i <= x; i++) {
			ans *= n;
			ans %= mod;
			n--;
		}
		long k = 1;
		long t = x;
		for (int i = 1; i <= t; i++) {
			k *= x;
			k %= mod;
			x--;
		}
//		BigInteger b = BigInteger.valueOf((k)).modInverse(BigInteger.valueOf((mod)));
		long b = modPow(k, mod - 2, mod);
		return ((b % mod) * ans) % mod;

	}

	public static long modInverse(long a, long m) {
		a = a % m;
		for (int x = 1; x < m; x++)
			if ((a * x) % m == 1)
				return x;
		return 1;
	}

	static long modPow(long a, long e, long mod) // O(log e)
	{
		a %= mod;
		long res = 1;
		while (e > 0) {
			if ((e & 1) == 1)
				res = (res * a) % mod;
			a = (a * a) % mod;
			e >>= 1;
		}
		return res % mod;
	}

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		PrintWriter pw = new PrintWriter(System.out);
		// pw=new PrintWriter("C:\\Users\\Hp\\Desktop\\outt.txt");

		int t=sc.nextInt();
	out:	while(t-->0) {
			int n=sc.nextInt();
			HashSet<Integer>hs=new HashSet<Integer>();
			boolean[]vis=new boolean[2*n+1]; 
			int[]Arr=new int[n];
			for(int i=0;i<n;i++) {
				int a=sc.nextInt();
				Arr[i]=a;
				vis[a]=true;
				hs.add(a);
			}
			ArrayList<Integer>arr=new ArrayList<Integer>();
			for(int i=0;i<n;i++) {
				int a=Arr[i];
				arr.add(Arr[i]);
				for(int j=a+1;j<=2*n;j++) {
					if(!vis[j]) {
						arr.add(j);
						vis[j]=true;
						break;
					}
				}
			}
			if(arr.size()!=2*n) {
				pw.print(-1);
			}else {
				for(int x:arr)
				pw.print(x+" ");
			}
			pw.println();
		
		}
		pw.close();
	}

	public static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public double nextDouble() throws IOException {
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if (x.charAt(0) == '-') {
				neg = true;
				start++;
			}
			for (int i = start; i < x.length(); i++)
				if (x.charAt(i) == '.') {
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				} else {
					sb.append(x.charAt(i));
					if (dec)
						f *= 10;
				}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg ? -1 : 1);
		}

		public boolean ready() throws IOException, IOException {
			return br.ready();
		}

	}
}