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.io.BufferedReader;
					import java.util.ArrayList;
					import java.util.Arrays;
					import java.util.Collections;
					import java.util.HashMap;
					import java.util.HashSet;
					import java.util.List;
					import java.util.Map;
					import java.io.IOException;
					import java.io.InputStreamReader;
				import java.math.BigInteger;
				import java.util.Scanner;
					import java.util.Set;
					import java.util.StringTokenizer;
				import java.util.Vector;
					
					
					
					
					public class ForLooops {
						 static class FastReader 
						    { 
						        BufferedReader br; 
						        StringTokenizer st; 
						       
						  
						        public FastReader() 
						        { 
						            br = new BufferedReader(new
						                     InputStreamReader(System.in)); 
						        } 
						  
						        String next() 
						        { 
						            while (st == null || !st.hasMoreTokens()) 
						            { 
						                try
						                { 
						                    st = new StringTokenizer(br.readLine()); 
						                } 
						                catch (IOException  e) 
						                { 
						                    e.printStackTrace(); 
						                } 
						            } 
						            return st.nextToken();
						            
						        } 
						  
						        int nextInt() 
						        { 
						            return Integer.parseInt(next()); 
						        } 
						  
						        long nextLong() 
						        { 
						            return Long.parseLong(next()); 
						        } 
						  
						        double nextDouble() 
						        { 
						            return Double.parseDouble(next()); 
						        } 
						  
						        String nextLine() 
						        { 
						            String str = ""; 
						            try
						            { 
						                str = br.readLine(); 
						            } 
						            catch (IOException e) 
						            { 
						                e.printStackTrace(); 
						            } 
						            return str; 
						        }
					
								public Character charAt(int i) {
									// TODO Auto-generated method stub
									return null;
								} 
								public BigInteger nextBigInteger() {
									// TODO Auto-generated method stub
									return null;
								} 
						    }
					
						 static int gcd(int a , int b) {
							 if(b==0)return a;
							 return gcd(b,a%b);
						 }
					
						/**
						 * @param args
						 * @throws IOException
						 */
						 static int m =(int) (1e9+7);
						 static long mod(long x) {
							 
							 return ((x%m+m)%m);
						 }
						 static long add(long x,long y) {
							 return mod((mod(x)+mod(y)));
						 }
						 static long mul(long x,long y) {
							 return mod((mod(x)*mod(y)));
						 }
						 
	
					
						public static void main(String[] args)throws IOException  {
							FastReader s=new FastReader();
							int t = s.nextInt();
							while(t-->0) {
								int n = s.nextInt();
								List<Integer> l = new ArrayList<>();
								List<Integer> a = new ArrayList<>();
								int flag=0;
								for(int i=0;i<n;i++) {
									l.add(s.nextInt());
									if(l.get(i)==2*n)flag=1;
								}
								if(flag==1)System.out.println("-1");
								else {
									for(int i=0;i<n;i++) {
										int k = l.get(i);
										k+=1;
										while(l.contains(k) || a.contains(k)) {
											k++;
										}
										if(k>2*n) {
											System.out.println("-1");
											flag=1;
											break;
										}
										a.add(k);
										
									}
									if(flag==1)continue;
									for(int i=0;i<n;i++) {
										System.out.print(l.get(i)+" "+a.get(i)+" ");
									}
									System.out.println();
								}
								
								
									
							}

						}
				}