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.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
import java.util.Arrays;

public class project 
{ 
    static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                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 static void main(String[] args) throws Exception 
    { 
            
            FastReader sc = new FastReader();
            int t=sc.nextInt();
            while(t>0){
                int i,m=1,p;
                int n=sc.nextInt();
                int b[]=new int[n];
                int a[]=new int[2*n+1];
                int f[]=new int[2*n+1];
                
                boolean flag=true;
                for(i=0;i<n;i++) b[i]=sc.nextInt();
                for(i=0;i<n;i++){
                    a[2*i+1]=b[i];
                    f[b[i]]++;
                }
                for(i=2;i<2*n+1;i=i+2){
                    m=1;
                    flag=true;
                    while(flag){
                        if(a[i-1]+m>2*n) {flag=false;break;}
                        else{
                        if(f[a[i-1]+m]==0)  break;
                        else if(f[a[i-1]+m]==1) m++;
                        }
                          
                    }
                   if(!flag) {System.out.print("-1");break;}
                   else{
                  a[i]= a[i-1]+m; f[a[i-1]+m]++;}
                }
                if(flag){
                for(i=1;i<2*n+1;i++) System.out.print(a[i]+" ");}
                System.out.print("\n");
                t--;
            }
            
    }
}