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.*;

import java.util.StringTokenizer;
import java.util.TreeSet;


public class Main {


    public static void main(String[] args) throws IOException {

        Scanner s = new Scanner(System.in);
        int tests = s.nextInt();
        while(tests--!=0){
           int n = s.nextInt();
           int freq[] = new int[2*n +1];
            int arr[] = new int[2*n +1];
            boolean flag = false;
            TreeSet<Integer>ts = new TreeSet<>();
            for(int i=0;i<2*n;i+=2){
                arr[i]= s.nextInt();
                freq[arr[i]]++;
            }
            for(int i=1;i<=2*n;i++){
                if(freq[i]==0)ts.add(i);
            }
            for(int i=1;i<=2*n;i+=2){
                int x = arr[i-1];
                if(ts.ceiling(x)==null){
                    flag=true;
                    break;
                }
                else{
                    arr[i]=ts.ceiling(x);
                    ts.remove(arr[i]);
                }
            }
            if(flag) System.out.println(-1);
            else{
                for(int i=0;i<2*n;i++){
                    System.out.print(arr[i]+" ");
                }
                System.out.println();
            }

        }

    }
}




class Scanner
{
    StringTokenizer st;
    BufferedReader br;

    public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}

    public String next() throws IOException
    {
        while (st == null || !st.hasMoreTokens())
            st = new StringTokenizer(br.readLine());
        return st.nextToken();
    }

    public int nextInt() throws IOException {return Integer.parseInt(next());}

    public long nextLong() throws IOException {return Long.parseLong(next());}

    public String nextLine() throws IOException {return br.readLine();}

    public double nextDouble() throws IOException
    {
        String x = next();
        StringBuilder sb = new StringBuilder("0");
        double res = 0, f = 1;
        boolean dec = false, neg = false;
        int start = 0;
        if(x.charAt(0) == '-')
        {
            neg = true;
            start++;
        }
        for(int i = start; i < x.length(); i++)
            if(x.charAt(i) == '.')
            {
                res = Long.parseLong(sb.toString());
                sb = new StringBuilder("0");
                dec = true;
            }
            else
            {
                sb.append(x.charAt(i));
                if(dec)
                    f *= 10;
            }
        res += Long.parseLong(sb.toString()) / f;
        return res * (neg?-1:1);
    }

    public boolean ready() throws IOException {return br.ready();}


}