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 com.company;
        import java.io.BufferedReader;
        import java.io.IOException;
        import java.io.InputStreamReader;
        import java.lang.reflect.Array;
        import java.sql.SQLOutput;
        import java.util.*;
        public class Main {

            public static void main(String[] args) throws IOException {
                Scanner s = new Scanner(System.in);
                //BufferedReader s=new BufferedReader(new InputStreamReader(System.in));
                 StringBuilder sb1 = new StringBuilder();//int n=Integer.parseInt(s.readLine());
            int t=s.nextInt();
            while(t-->0){
            int n=s.nextInt();
            int[] a=new int[n+1];
            int[] b=new int[2*n+1];
            int[] ind=new int[2*n+1];
            Arrays.fill(ind,-1);
            int flag=0;
            for(int i=1;i<=n;i++){
                a[i]=s.nextInt();
                b[2*i-1]=a[i];
                ind[a[i]]=2*i-1;
            }Queue<Integer> q=new LinkedList<Integer>();
            for(int i=1;i<=2*n;i++){flag=-1;
              if(b[i]==0) {
                  for (int j = b[i-1] + 1; j <= 2 * n; j++) {
                      if (ind[j] == -1) {
                          flag = 0;
                          b[i] = j;
                          ind[j] = i;
                          break;
                      }
                  }
                  if (flag == -1) break;
              }}
            if(flag!=-1){
            for(int i=1;i<=2*n;i++){
                sb1.append(b[i]+" ");
            }}else sb1.append(-1);
            sb1.append("\n");
            }
                System.out.println(sb1.toString());
            }static int min=Integer.MAX_VALUE;static long ans=0;static long count=0;
            static void dfs(int i,int[] vis,HashMap<Integer,Integer> h,int [] a,int[] c,int ts){
              //if(vis[i]!= vis1[i]) return;
                if(vis[i]>0&&(!h.containsKey(i)||h.get(i)!=vis[i])) return;

                if(vis[i]==2) return;
                if(h.containsKey(i)&&h.get(i)==2) return;
                if(h.containsKey(i))  h.put(i,h.get(i)+1);
                else h.put(i,1);
                vis[i]+=1;
                //vis1[i]+=1;
                if(h.get(i)==2) min=Math.min(min,c[i])    ;
            //    if(vis[i]==1) min=c[i];
                dfs(a[i],vis,h,a,c,ts);
            }
            static  void computeLPSArray(String pat, int M, int lps[])
            {
            int len = 0;
                int i = 1;
                lps[0] = 0;
                while (i < M) {
                    if (pat.charAt(i) == pat.charAt(len)) {
                        len++;
                        lps[i] = len;
                        i++;
                    }
                    else // (pat[i] != pat[len])
                    {
                        if (len != 0) {
                            len = lps[len - 1];
                        }
                        else // if (len == 0)
                        {
                            lps[i] = len;
                            i++;
                        }
                    }
                }
            }
            static boolean isPrime(int n)
            {
                if (n <= 1) return false;
                if (n <= 3) return true;

                if (n % 2 == 0 || n % 3 == 0) return false;

                for (int i = 5; i * i <= n; i = i + 6)
                    if (n % i == 0 || n % (i + 2) == 0)
                        return false;

                return true;
            }

            static double power(double x, long y, int p) {
                double res = 1;
                x = x % p;
                while (y > 0) {
                    if ((y & 1) == 1)
                        res = (res * x) % p;
                    y = y >> 1;
                    x = (x * x) % p;
                }
                return res;
            }
            public static void fracion(double x) {
                String a = "" + x;
                String spilts[] = a.split("\\."); // split using decimal
                int b = spilts[1].length(); // find the decimal length
                int denominator = (int) Math.pow(10, b); // calculate the denominator
                int numerator = (int) (x * denominator); // calculate the nerumrator Ex
                // 1.2*10 = 12
                int gcd = (int)gcd((long)numerator, denominator); // Find the greatest common
                // divisor bw them
                String fraction = "" + numerator / gcd + "/" + denominator / gcd;
                // System.out.println((denominator/gcd));
                long x1=modInverse(denominator / gcd,998244353  );
                //  System.out.println(x1);
                System.out.println((((numerator / gcd )%998244353 *(x1%998244353  ))%998244353  ) );
            }static int anst=Integer.MAX_VALUE;
          static StringBuilder sb1=new StringBuilder();
            public static int bfs(int i1, ArrayList<Integer>[] h, int[] vis, int n,int val1) {
                Queue<Integer> q = new LinkedList<Integer>();
                q.add(i1);Queue<Integer> aq=new LinkedList<Integer>();
                aq.add(0);
                while(!q.isEmpty()){
                    int i=q.poll();
                    int val=aq.poll();
                    if(i==n){
                        return val;
                    }
                    if(h[i]!=null){
                        for(Integer j:h[i]){
                           if(vis[j]==0){
                            q.add(j);vis[j]=1;
                               aq.add(val+1);}
                        }
                    }
                }return -1;
            }
            static int i(String a) {
                return Integer.parseInt(a);
            }
            static long l(String a) {
                return Long.parseLong(a);
            }
            static String[] inp() throws IOException {
                BufferedReader s = new BufferedReader(new InputStreamReader(System.in));
                return s.readLine().trim().split("\\s+");
            }


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


                {
                    // If a and m are relatively prime, then modulo inverse
                    // is a^(m-2) mode m
                    return (power(a, m - 2, m));
                }
            }

            // To compute x^y under modulo m
            static long power(int x, int y, int m)
            {
                if (y == 0)
                    return 1;

                long p = power(x, y / 2, m) % m;
                p = (p * p) % m;

                if (y % 2 == 0)
                    return p;
                else
                    return (x * p) % m;
            }

            // Function to return gcd of a and b

        }
        class Student
        {
            int l;int r;
            public Student(int l, int r) {
                this.l = l;
                this.r = r;
            }
            // Constructor


            // Used to print student details in main()
            public String toString()
            {
                return this.l+" ";
            }
        }

        class Sortbyroll implements Comparator<Student>
        {
            // Used for sorting in ascending order of
            // roll number
            public int compare(Student a, Student b){
                return a.l-b.l;  }
        } class Sortbyroll1 implements Comparator<Student>
        {
            // Used for sorting in ascending order of
            // roll number
            public int compare(Student a, Student b){
               if(a.r==b.r) return a.l-b.l;
                return a.r-b.r;
            }
        }