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:
// Working program with FastReader 
import java.io.BufferedReader; 
import java.io.IOException; 
import java.io.InputStreamReader; 
import java.util.*;
public class ll
{ 
    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 final int MAXN = 10000001;

    // stores smallest prime factor for every number
    static int spf[] = new int[MAXN];

    // Calculating SPF (Smallest Prime Factor) for every
    // number till MAXN.
    // Time Complexity : O(nloglogn)
    static void sieve()
    {
        spf[1] = 1;
        for (int i=2; i<MAXN; i++)

        // marking smallest prime factor for every
        // number to be itself.
            spf[i] = i;

        // separately marking spf for every even
        // number as 2
        for (int i=4; i<MAXN; i+=2)
            spf[i] = 2;

        for (int i=3; i*i<MAXN; i++)
        {
            // checking if i is prime
            if (spf[i] == i)
            {
                // marking SPF for all numbers divisible by i
                for (int j=i*i; j<MAXN; j+=i)

                // marking spf[j] if it is not
                // previously marked
                    if (spf[j]==j)
                        spf[j] = i;
            }
        }
    }

    // A O(log n) function returning primefactorization
    // by dividing by smallest prime factor at every step
    static int getFactorization(int x)
    {
        int c=0;
        while (x != 1)
        {
            c++;
            x = x / spf[x];
        }
        return c;
    }

    static int LowerBound(int a[], int x) { // x is the target value or key
        int l=-1,r=a.length;
        while(l+1<r) {
            int m=(l+r)>>>1;
            if(a[m]>=x) r=m;
            else l=m;
        }
        return r;
    }

    static int UpperBound(int a[], int x) {// x is the key or target value
        int l=-1,r=a.length;
        while(l+1<r) {
            int m=(l+r)>>>1;
            if(a[m]<=x) l=m;
            else r=m;
        }
        return l+1;
    }

    static void ruffleSort(long[] a) {
        int n=a.length;
        Random r=new Random();
        for (int i=0; i<a.length; i++) {
            long oi=r.nextInt(n), temp=a[i];
            a[i]=a[(int)oi];
            a[(int)oi]=temp;
        }
        Arrays.sort(a);
    }

    static void ruffleSort(int[] a) {
        int n=a.length;
        Random r=new Random();
        for (int i=0; i<a.length; i++) {
            int oi=r.nextInt(n), temp=a[i];
            a[i]=a[oi];
            a[oi]=temp;
        }
        Arrays.sort(a);
    }

    public static int findIndex(long arr[], long t) 
    { 

        // if array is Null 
        if (arr == null) { 
            return -1; 
        } 

        // find length of array 
        int len = arr.length; 
        int i = 0; 

        // traverse in the array 
        while (i < len) { 

            // if the i-th element is t 
            // then return the index 
            if (arr[i] == t) { 
                return i; 
            } 
            else { 
                i = i + 1; 
            } 
        } 
        return -1; 
    }

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

    // method to return LCM of two numbers
    static int lcm(int a, int b)
    {
        return (a / gcd(a, b)) * b;
    }

    public static int[] swap(int a[], int left, int right)
    {

        // Swap the data
        int temp = a[left];
        a[left] = a[right];
        a[right] = temp;

        // Return the updated array
        return a;
    }

    public static int[] reverse(int a[], int left, int right)
    {

        // Reverse the sub-array
        while (left < right) {
            int temp = a[left];
            a[left++] = a[right];
            a[right--] = temp;
        }

        // Return the updated array
        return a;
    }

    public static int[] findNextPermutation(int a[])
    {
        int last = a.length - 2;

        // find the longest non-increasing suffix
        // and find the pivot
        while (last >= 0) {
            if (a[last] < a[last + 1]) {
                break;
            }
            last--;
        }

        // If there is no increasing pair
        // there is no higher order permutation
        if (last < 0)
            return a;

        int nextGreater = a.length - 1;

        // Find the rightmost successor to the pivot
        for (int i = a.length - 1; i > last; i--) {
            if (a[i] > a[last]) {
                nextGreater = i;
                break;
            }
        }

        // Swap the successor and the pivot
        a = swap(a, nextGreater, last);

        // Reverse the suffix
        a = reverse(a, last + 1, a.length - 1);

        // Return true as the next_permutation is done
        return a;
    }

    static void sort(int[] a) {
        ArrayList<Integer> l = new ArrayList<>();
        for (int i : a)
            l.add(i);
        Collections.sort(l);
        for (int i = 0; i < a.length; i++)
            a[i] = l.get(i);
    }

    static double pow(double p,double tt)
    {
        double ii,q,r;
        q=1;
        r=p;
        while(tt>1)
        {
            for(ii=1;2*ii<=tt;ii*=2)
                p*=p;
            tt-=ii;
            q*=p;
            p=r;
        }
        if(tt==1)
            q*=r;
        return q;
    }

    static int factorial(int n)
    {
        return (n == 1 || n == 0) ? 1 : n * factorial(n - 1);
    }

    public static int primeFactors(int n)
    {
        int c=0;
        // Print the number of 2s that divide n
        while (n%2==0)
        {
            c++;
            n /= 2;
        }

        // n must be odd at this point.  So we can
        // skip one element (Note i = i +2)
        for (int i = 3; i <= Math.sqrt(n); i+= 2)
        {
            // While i divides n, print i and divide n
            while (n%i == 0)
            {
                c++;
                n /= i;
            }
        }

        // This condition is to handle the case whien
        // n is a prime number greater than 2
        if (n > 2)
            c++;
        return c;
    }

    static void PrimeList(){
        int i,j;
        int sieve[]=new int[100001];
        for(i=2;i*i<=100000;i++)
        {
            if(sieve[i]==0)
            {
                for(j=i*i;j<=100000;j+=i)
                    sieve[j]=1;
            }
        }
        ArrayList<Integer> primes=new ArrayList<>();
        for(i=2;i<=100000;i++)
        {
            if(sieve[i]==0)
                primes.add(i);
        }
    }

    public static void main(String[] args) 
    {
        //try
        //{
        FastReader d=new FastReader();
        int t,i,j,c,z,k,l,r,n,q;
        int mod = (int) 1e9 + 7;

        int Inf=Integer.MAX_VALUE;
        int negInf=Integer.MIN_VALUE;
        t=d.nextInt();
        //t=1;
        String s;
        //char ch,ch1,ch2,ch3;
        long ans;

        while(t-->0)
        {
            z=c=0;
            ans=0l;
            n=d.nextInt();
            int a[]=new int[n];
            for(i=0;i<n;i++)
            a[i]=d.nextInt();
            int b[]=new int[2*n];
            j=0;
            int num[]=new int[2*n+1];
            for(i=0;i<2*n+1;i++)
            num[i]=i;
            for(i=0;i<n;i++)
            num[a[i]]=0;
            for(i=0;i<n;i++)
            {
                b[j]=a[i];
                for(k=a[i];k<=2*n;k++)
                {
                    if(num[k]!=0)
                    {
                        b[j+1]=num[k];
                        num[k]=0;
                        z=1;
                        break;
                    }
                }
                if(z==0)
                {
                    c=1;
                break;
            }
                else
                {
                    j+=2;
                    z=0;
                }
            }
            if(c==1)
            System.out.println(-1);
            else
            {
                for(i=0;i<2*n;i++)
                System.out.print(b[i]+" ");
                System.out.println();
                }
            //dont need extra d.nextLine()
        }
        /*
        }catch(Exception e) {
        System.out.println(0);
        }*/
    }
}