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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

import javax.swing.JInternalFrame;

public class Main
{
	public static void main(String[] args) throws IOException
	{
		StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		
		in.nextToken();
		int num = (int)in.nval;
		
		for(int i = 0; i < num; i++)
		{
			in.nextToken();
			int num1 = (int)in.nval;
			int[] getLine = new int[num1];
			int[] numLine = new int[210];
			for(int j = 0; j < num1; j++)    {    in.nextToken();    int num2 = (int)in.nval;    numLine[num2]++;    getLine[j] = num2;    }
			int haveYES = 1;
			int numHave = 0;
			for(int j = 1; j < num1 * 2; j++)
			{
				if(numLine[j] > 1)    {    haveYES = 0;    break;    }
				if(numLine[j] == 1)    numHave++;
				if(j % 2 == 1)
					if(numHave < j / 2 + 1)    {    haveYES = 0;    break;    }
			}
			if(haveYES == 0)    {    out.println("-1");    continue;    }
			for(int j = 0; j < num1; j++)
			{
				out.print(getLine[j] + " ");
				for(int k = getLine[j] + 1; ; k++)
				{
					if(numLine[k] == 0)
					{
						out.print(k + " ");
						numLine[k] = 1;
						break;
					}
				}
			}
			out.println();
		}
		out.flush();
	}
}