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.Scanner;
import java.util.StringTokenizer;
import java.io.*;
import java.util.*;
import java.text.DecimalFormat;
import java.math.*;

public class Main {

static int  mod = 1000000007;
/*****************code By Priyanshu *******************************************/ 

    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;
        }
    }
    // this > other return +ve
    // this < other return -ve
    // this == other return 0
     public static class Pair implements Comparable<Pair> {
      int st;
      int et;

      public Pair(int st, int et) {
         this.st = st;
         this.et = et;
      }

      public int compareTo(Pair other) {
         if (this.st != other.st) {
            return this.st - other.st;
         } else {
            return this.et - other.et;
         }
      }
   }

    static long fastPower(long a, long b, int n) {
            
            long res = 1;
            
            while ( b > 0) {
                
                if ( (b&1) != 0) {
                    res = (res * a % n) % n;
                }
                
                a = (a % n * a % n) % n;
                b =  b >> 1;
            }
            
            return res;
            
        }

     // function to find
    // the rightmost set bit
    static int PositionRightmostSetbit(int n)
    {
        // Position variable initialize
        // with 1 m variable is used to
        // check the set bit
        int position = 1;
        int m = 1;
 
        while ((n & m) == 0) {
 
            // left shift
            m = m << 1;
            position++;
        }
        return position;
    }
    
         // used for swapping ith and jth elements of array
      // public static void swap(int[] arr, int i, int j) {
      //   int temp = arr[i];
      //   arr[i] = arr[j];
      //   arr[j] = temp;
      // }
        public static void swap(long i, long j) {
        long temp = i;
        i = j;
        j = temp;
      }


    static boolean palindrome(String s) {
        return new StringBuilder(s).reverse().toString().equals(s);
    }


    static int countDigit(long n)
    {
        return (int)Math.floor(Math.log10(n) + 1);
    }
  static boolean isPerfectSquare(double x)
    {
            double sr = Math.sqrt(x);
            return ((sr * sr) == x);     
    }


 public static int gcd(int a, int b)
    {
      if (b == 0)
        return a;
      return gcd(b, a % b);
    }
    
   

   static int nod(long l) {
       if(l>=1000000000000000000l) return 19;
       if(l>=100000000000000000l) return 18;
       if(l>=10000000000000000l) return 17;
       if(l>=1000000000000000l) return 16;
       if(l>=100000000000000l) return 15;
       if(l>=10000000000000l) return 14;
       if(l>=1000000000000l) return 13;
       if(l>=100000000000l) return 12;
       if(l>=10000000000l) return 11;
       if(l>=1000000000) return 10;
       if(l>=100000000) return 9;
       if(l>=10000000) return 8;
       if(l>=1000000) return 7;
       if(l>=100000) return 6;
       if(l>=10000) return 5;
       if(l>=1000) return 4;
       if(l>=100) return 3;
       if(l>=10) return 2;
       return 1;
    }
      //Arrays.sort(a,(c,d) -> Integer.compare(c[0],d[0]));

    
    public static boolean areAllBitsSet(int n )
    {
        // all bits are not set
        if (n == 0)
            return false;
     
        // if true, then all bits are set
        if (((n + 1) & n) == 0)
            return true;
     
        // else all bits are not set
        return false;
    }
   
 

        public static int[] radixSort2(int[] a)
    {
        int n = a.length;
        int[] c0 = new int[0x101];
        int[] c1 = new int[0x101];
        int[] c2 = new int[0x101];
        int[] c3 = new int[0x101];
        for(int v : a) {
            c0[(v&0xff)+1]++;
            c1[(v>>>8&0xff)+1]++;
            c2[(v>>>16&0xff)+1]++;
            c3[(v>>>24^0x80)+1]++;
        }
        for(int i = 0;i < 0xff;i++) {
            c0[i+1] += c0[i];
            c1[i+1] += c1[i];
            c2[i+1] += c2[i];
            c3[i+1] += c3[i];
        }
        int[] t = new int[n];
        for(int v : a)t[c0[v&0xff]++] = v;
        for(int v : t)a[c1[v>>>8&0xff]++] = v;
        for(int v : a)t[c2[v>>>16&0xff]++] = v;
        for(int v : t)a[c3[v>>>24^0x80]++] = v;
        return a;
    }

   






    public static void main(
        String[] args)
    {
        try {
            System.setIn(new FileInputStream("input.txt"));
            System.setOut(new PrintStream(new FileOutputStream("output.txt")));
        } catch (Exception e) {
            System.err.println("Error");
        }
          FastReader sc = new FastReader();
       
        int t = Integer.parseInt(sc.next());
      //  int t = 1;
 
        
     while(t-->0){

        int n = sc.nextInt();

       
        HashSet<Integer> s = new HashSet<Integer>();
    

        int a[] = new int[n];

        for (int i = 0; i<n; i++) {
            a[i] = sc.nextInt();
            s.add(a[i]);
        }
        int ans[] = new int [2*n];
        boolean c = false;

        for (int i = 0; i<n; i++) {
           
           int start = 2*i;
           int end = start +1;
           int val = a[i];

            int next = val +1;

            while(s.contains(next)){
                next++;
            }

            if(next > 2*n){
                System.out.println("-1");
                System.out.flush();
                c = true;
                break;
                
            }

            ans[start] = val;
            ans[end] = next;

            s.add(next);

        }

        if(!c){

             for (int i : ans ) {
            System.out.print(i + " ");
        }

        System.out.println();
        System.out.flush();


        }

       


     

       
         



      

     


       
        
          
       
        

       
        

        
        
       





    }    
  }
}
//code By Priyanshu