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.io.IOException; 
import java.io.InputStreamReader; 
import java.util.StringTokenizer; 
import java.util.*;
 
public class Solution 
{ 
   
    public static void main(String[] args) throws IOException 
    { 
  
       BufferedReader br = new BufferedReader( 
                              new InputStreamReader(System.in));
        StringBuilder out=new StringBuilder(); 
        int t=Integer.parseInt(br.readLine());
      for(int j=0;j<t;j++){
            int n=Integer.parseInt(br.readLine());
             int[] arr=new int[n];
             StringTokenizer s=new StringTokenizer(br.readLine());
             boolean not_one=true;
            boolean maximum=false; 
             for(int i=0;i<n;i++){
                 arr[i]=Integer.parseInt(s.nextToken());
                 if(arr[i]==1)
                 not_one=false;
                 if(arr[i]==(2*n))
                 maximum=true;
             }
             if(not_one|| maximum)
             {
                 out.append("-1"+"\n");
                 continue;
             }
          int[] ans=new int[2*n];
        HashSet<Integer>h=new HashSet<>();
        
        for(int i=0;i<n;i++){
        ans[2*i]=arr[i];
        
            h.add(arr[i]);
        }
        boolean o=false;
        for(int i=1;i<2*n;i=i+2){
            int k=ans[i-1];
            while(k<=2*n && h.contains(k))
            k++;
            if(k==2*n+1){
                  out.append("-1"+"\n");
                 o=true;
                 break;
            }
            
            ans[i]=k;
            h.add(k);
        }
        if(o==true)
        continue;
            
            for(int i=0;i<2*n;i++){
                out.append(ans[i]+" ");
            }
            out.append("\n");
        }
        
        
      
      System.out.println(out);
    }
}
 class Segment{
    int s;
    int e;
    public Segment(int x,int y){
        s=x;
        e=y;
    }
     
 }
class SortSeg implements Comparator<Segment> 
{ 
    // Used for sorting in ascending order of 
    // roll number 
    public int compare(Segment a, Segment b) 
    { 
        int lena= a.e-a.s+1;
         int lenb= b.e-b.s+1;
        if(lena==lenb)
        return a.s - b.s; 
        else
        //decsending order
        return lenb-lena;
    } 
}