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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.*;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

public class Two {

    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskA solver = new TaskA();
        int t;
        t = in.nextInt();
        //t = 1;
        while (t > 0) {
            solver.call(in,out);
            t--;
        }
        out.close();
    }

    static class TaskA {
        public void call(InputReader in, PrintWriter out) {
            int n , a=0 ,b =0;
            n = in.nextInt();

            int[] arr = new int[n];
            int[] array = new int[2*n+1];
            ArrayList<Integer> arrayList = new ArrayList<>();

            for (int i = 0; i < n; i++) {
                arr[i] = in.nextInt();
                array[arr[i]]++;
                if(arr[i]==2*n)
                    a++;
                if(arr[i]==1)
                    b++;

            }
            if(a!=0 || b==0){
                out.println(-1);
            }
            else{
                for (int i = 0; i < n; i++) {
                    arrayList.add(arr[i]);
                    for (int j = arr[i]+1; j <array.length ; j++) {
                        if(array[j]==0){
                            arrayList.add(j);
                            array[j]++;
                            break;
                        }
                    }
                }

                if(arrayList.size()==2*n){
                    for (int i=0;i<arrayList.size();i++)
                        out.print(arrayList.get(i)+" ");

                    out.println();
                }
                else
                    out.println(-1);



            }





        }
    }

    static class answer implements Comparable<answer>{
        int a, b;

        public answer(int a, int b) {
            this.a = a;
            this.b = b;
        }


        @Override
        public int compareTo(answer o) {
            return this.a - o.a;
        }
    }


    static long lcm(long a , long b){
        return (a/gcd(a,b)) *b;
    }

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


    static final Random random=new Random();
    static void shuffleSort(int[] arr) {
        int n = arr.length;
        for (int i=0; i<n; i++) {

            int a=random.nextInt(n), temp=arr[a];
            arr[a]=arr[i];
            arr[i]=temp;

        }

        Arrays.sort(arr);

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }
        public long nextLong(){
            return Long.parseLong(next());
        }

    }
}