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 static java.lang.Integer.numberOfTrailingZeros;
import static java.lang.Integer.parseInt;
import static java.lang.Long.parseLong;
import static java.lang.Short.parseShort;
import static java.lang.Byte.parseByte;
import java.io.*;
import java.util.*;

public class Contest {

    static int nextInt() throws IOException {
        return parseInt(next());
    }

    static long nextLong() throws IOException {
        return parseLong(next());
    }

    static short nextShort() throws IOException {
        return parseShort(next());
    }

    static byte nextByte() throws IOException {
        return parseByte(next());
    }

    static String next() throws IOException {
        while (tok == null || !tok.hasMoreTokens())
            tok = new StringTokenizer(in.readLine());
        return tok.nextToken();
    }

    static String nextLine() throws IOException {
        return in.readLine();
    }

    private static BufferedReader in;
    private static StringTokenizer tok;
    private static PrintWriter out = new PrintWriter(System.out);
    private static Utilities doThis = new Utilities(out);
    private static MyMath doMath = new MyMath();

    public static void main(String[] args) throws Exception {
        in = new BufferedReader(new InputStreamReader(System.in));

        /*--------------------SolutionStarted-------------------*/
        solve();
        /*--------------------SolutionEnded--------------------*/

        in.close();
        out.close();
    }


    static int n, m, k,
            count = 0, length = 0, sum = 0,
            q, t,
            idx, temp;
    static char[] s, s1;
    static int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
    static long lMax = Long.MAX_VALUE, lMin = Long.MIN_VALUE, lSum = 0, lCount;
    static int[] nums;
    static boolean flag;

    static void solve() throws IOException {
        t = nextInt();
        whl:
        while(t-->0){
            int[] b = new int[nextInt()];
            HashSet<Integer> set = new HashSet<>();
            for (int i = 0; i < b.length; i++)
                set.add(b[i]=nextInt());
              
            int[]a =new int[1+(b.length*2)];
            for (int i = 0; i < b.length; i++) {
                temp = i+1;
                a[(temp*2)-1] = b[i];
                for (int j = b[i]; true; j++) {
                    if(!set.contains(j)){
                        set.add(j);
                        a[(temp*2)]=j;
                        break;
                    }
                }
            }
            for (int i = 1; i <=b.length*2; i++) {
                if(!set.contains(i)){
                    doThis.bad();
                    continue whl;
                }
            }
            for (int i = 1; i <a.length; i++) {
                out.print(a[i]+" ");
            }
            out.println();
        }
    }
}
class Pair implements Comparable<Pair>{
    int k,v;
    boolean taken;
    Pair(int k,int v){
        this.k = k;
        this.v =v;
    }

    @Override
    public int compareTo(Pair o) {
        return v-o.v;
    }
}
class CharPair{
    char ch;
    int value;
    CharPair(char c, int v){
        ch =c; value=v;
    }
    char get(){
        return ch;
    }
}
class IntPair implements Comparable<IntPair> {
    int key, value;
    IntPair(int key, int value) {
        this.key = key;
        this.value = value;
    }

    @Override
    public int compareTo(IntPair o) {
        if (value == o.value)
            return key - o.key;
        return value - o.value;
    }

    public String toString() {
        return key + " " + value;
    }
}
class BooleanPair {
    boolean key, value;

    BooleanPair() {
    }

    BooleanPair(boolean key, boolean value) {
        this.key = key;
        this.value = value;
    }
}
class Utilities {
    PrintWriter out;
    Utilities(PrintWriter out){
        this.out = out;
    }
    //int arrays start
    int lowerBound(int[] arr, int low, int high, int element) {
        int middle;
        while (low < high) {
            middle = low + (high - low) / 2;
            if (element > arr[middle])
                low = middle + 1;
            else
                high = middle;
        }
        if (arr[low] < element)
            return -1;
        return low;
    }

    int upperBound(int[] arr, int low, int high, int element) {
        int middle;
        while (low < high) {
            middle = low + (high - low) / 2;
            if (arr[middle] > element)
                high = middle;
            else
                low = middle + 1;
        }
        if (arr[low] <= element)
            return -1;
        return low;
    }
    //int arrays end
    //long arrays start
    int lowerBound(long[] arr, int low, int high, long element) {
        int middle;
        while (low < high) {
            middle = low + (high - low) / 2;
            if (element > arr[middle])
                low = middle + 1;
            else
                high = middle;
        }
        if (arr[low] < element)
            return -1;
        return low;
    }

    int upperBound(long[] arr, int low, int high, long element) {
        int middle;
        while (low < high) {
            middle = low + (high - low) / 2;
            if (arr[middle] > element)
                high = middle;
            else
                low = middle + 1;
        }
        if (arr[low] <= element)
            return -1;
        return low;
    }
    //long arrays end
    //double arrays start
    int lowerBound(double[] arr, int low, int high, double element) {
        int middle;
        while (low < high) {
            middle = low + (high - low) / 2;
            if (element > arr[middle])
                low = middle + 1;
            else
                high = middle;
        }
        if (arr[low] < element)
            return -1;
        return low;
    }

    int upperBound(double[] arr, int low, int high, double element) {
        int middle;
        while (low < high) {
            middle = low + (high - low) / 2;
            if (arr[middle] > element)
                high = middle;
            else
                low = middle + 1;
        }
        if (arr[low] <= element)
            return -1;
        return low;
    }
    //double arrays end
    int arrUp(int [][]arr,int i, int j){
        if(i==0)
            return Integer.MIN_VALUE;
        return arr[i-1][j];
    }
    int arrDown(int [][]arr,int i, int j){
        if(i==arr.length-1)
            return Integer.MIN_VALUE;
        return arr[i+1][j];
    }
    int arrLeft(int [][]arr,int i, int j){
        if(j==0)
            return Integer.MIN_VALUE;
        return arr[i][j-1];
    }
    int arrRight(int [][]arr,int i, int j){
        if(j==arr[i].length-1)
            return Integer.MIN_VALUE;
        return arr[i][j+1];
    }
    int count(char[] s, char c){
        int count = 0;
        for (int i = 0; i < s.length; i++) {
            if (s[i]==c)
                count++;
        }
        return count;
    }
    void swap(char[] s, int a,int b){
        char temp =s[b];
        s[b]= s[a];
        s[a] = temp;
    }
    boolean odd(int a){
        return a%2==1;
    }
    boolean even(int a){
        return a%2==0;
    }
    void yes(){
        out.println("YES");
    }
    void no() {
        out.println("NO");
    }
    void bad(){
        out.println(-1);
    }
    void printBinary(int num){
        out.println(Integer.toBinaryString(num));
    }
}
class MyMath {
    boolean isCoPrime(int a, int b) {
        return gcd(a, b) == 1;
    }

    int gcd(int a, int b) {
        if (a == 0)
            return b;
        while (b != 0)
            if (a > b)
                a = a - b;
            else
                b = b - a;
        return a;
    }

    int log2(int x) {
        return (int) (Math.log(x) / Math.log(2));
    }
    boolean[] sieveOfEratosthenes(int n)
    {
        // Create a boolean array "primes[0..n]" and initialize
        // all entries it as true. A value in primes[i] will
        // finally be false if i is Not a primes, else true.
        boolean primes[] = new boolean[n+1];
        for(int i=0;i<n;i++)
            primes[i] = true;

        for(int p = 2; p*p <=n; p++)
        {
            // If primes[p] is not changed, then it is a primes
            if(primes[p])
            {
                // Update all multiples of p
                for(int i = p*p; i <= n; i += p)
                    primes[i] = false;
            }
        }
        return primes;
    }
}
class Bitmasks{
    static byte andBitmask(byte state, byte... masks){
        byte temp=0;
        for (int i = 0; i < masks.length; i++) {
            temp|=masks[i];
        }
        return (byte) (state&temp);
    }
    static byte toggleBitmask(byte state ,byte... masks){
        return state;
    }
    static byte removeBitmask(byte state, byte... masks){
        return state;
    }
    static byte addBitmask(byte state ,byte... masks){
        return state;
    }
}