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.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.*;
import java.util.Queue;
import java.util.StringTokenizer;
import java.math.BigInteger;
 
 
  public class hello2
 {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; 
           } 
         
       }
    
    static String sum (String s)
    {
        String s1 = ""; 
        
        if(s.contains("a"))
            s1+="a";
        if(s.contains("e"))
            s1+="e";
        if(s.contains("i"))
            s1+="i";
        if(s.contains("o"))
            s1+="o";
        if(s.contains("u"))
            s1+="u";
        
            return s1;
            
        
    }
    
 
    public static void main(String[] args) 
    { 
       FastReader sc =new FastReader();
       int t=sc.nextInt();
       while(t-->0)
{       
       int n=sc.nextInt();
       int[] b=new int[n];
        int min = Integer.MAX_VALUE;
          int max = Integer.MIN_VALUE;
          for(int i=0;i<n;i++){
              b[i]=sc.nextInt();
              if(max<b[i]){
                  max=b[i];
              }
              if(min>b[i]){
                  min=b[i];
              }
          }
          if(max==2*n){
              System.out.println(-1);
              continue;
          }
          else if(min!=1){
              System.out.println(-1);
              continue;
          }
          else{
              int arr[] = new int[2*n];
              int count[] = new int[2*n+1];
              int ind=0;
              for(int i=0;i<n;i++){
                  arr[ind]=b[i];
                  count[arr[ind]]=1;
                  ind+=2;
              }
              int f=0;
              for(int i=0;i<2*n;i++){
                  if(arr[i]>0){continue;}
                  else{
                      int x = arr[i-1]+1;
                      while(x<=2*n && count[x]==1){
                          x++;
                      }
                      if(x>2*n){
                          x=1;
                          while(x<=2*n && count[x]==1){
                              x++;
                          }
                          if(x<arr[i-1]){
                              f=1;
                              break;
                          }
                          arr[i]=x;
                          count[x]=1;
                      }
                      else{
                          arr[i]=x;
                          count[x]=1;
                      }
                  }
                  
              }
              if(f==1){
                  System.out.println(-1);
                  continue;
              }
              for(int i=0;i<2*n;i++){
                  System.out.print(arr[i]+" ");
              }
              System.out.println();
          }
       }
    }
 }