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:
/* package codechef; // don't place package name! */
// for(i=0;i<n;i++)
// for(j=0;j<n;j++)
// int n=sc.nextInt();
// int a[]=new int[n];
// a[i]=sc.nextInt();
// ArrayList<Integer> ar=new ArrayList<Integer>();
// System.out.println();
//  HashMap<String, Integer> map 
//            = new HashMap<>(); 

import java.util.*;
import java.lang.*;
import java.io.*;

public class Codeforces
{ 
	

	 
	public static void main(String args[]) 
	{ 
        Scanner sc = new Scanner(System.in);
		
	
	int t=sc.nextInt();
		while(t-->0)
	    {int i;
	       int n =sc.nextInt();
	        ArrayList <Integer> ar=new ArrayList<Integer>();
	        for(i=0;i<2*n;i++)
	        ar.add(i+1);
	     //  System.out.println(ar); 
	       int a[]=new int[n];
	       int found=0,find=0;
	       for(i=0;i<n;i++)
	       {
	           a[i]=sc.nextInt();
	           if(a[i]==1)
	           find=1;
	           if(a[i]==2*n)
	           found=1;
	           if(ar.contains(a[i]));
	           ar.remove(ar.indexOf(a[i]));
	       }
	  //      System.out.println(ar);
	       if(found==1||find==0){
	       System.out.println(-1);
	       continue;
	    }
	       if(n==1 && a[0]==1)
	       {
	           System.out.println(1+" "+2);
	           continue;
	       }
	  //     Collections.sort(ar);
	       String s="";
	       int c=0;
	       for(i=0;i<n;i++)
	       {
	           int x=a[i];
	           for(int j=0;j<ar.size();j++){
	           if(ar.get(j)>x){
	               s=s+x+" "+ar.get(j)+" ";
	               c++;
	               // System.out.println(s);
	               ar.remove(ar.indexOf(ar.get(j)));
	              //  System.out.println(ar);
	               break;
	           }
	       }
	       }
	       if(c!=n)
	       System.out.println(-1);
	       else
	       System.out.println(s);
	    }
	}
}