Problem: Permutation p is a sequence of integers p=[p_1, p_2, ..., p_n], consisting of n distinct (unique) positive integers between 1 and n, inclusive. For example, the following sequences are permutations: [3, 4, 1, 2], [1], [1, 2]. The following sequences are not permutations: [0], [1, 2, 1], [2, 3], [0, 1, 2].

The important key is in the locked box that you need to open. To open the box you need to enter secret code. Secret code is a permutation p of length n. 

You don't know this permutation, you only know the array q of prefix maximums of this permutation. Formally:

  * q_1=p_1, 
  * q_2=max(p_1, p_2), 
  * q_3=max(p_1, p_2,p_3), 
  * ... 
  * q_n=max(p_1, p_2,...,p_n). 



You want to construct any possible suitable permutation (i.e. any such permutation, that calculated q for this permutation is equal to the given array).

Input

The first line contains integer number t (1 ≤ t ≤ 10^4) — the number of test cases in the input. Then t test cases follow.

The first line of a test case contains one integer n (1 ≤ n ≤ 10^{5}) — the number of elements in the secret code permutation p.

The second line of a test case contains n integers q_1, q_2, ..., q_n (1 ≤ q_i ≤ n) — elements of the array q for secret permutation. It is guaranteed that q_i ≤ q_{i+1} for all i (1 ≤ i < n).

The sum of all values n over all the test cases in the input doesn't exceed 10^5.

Output

For each test case, print:

  * If it's impossible to find such a permutation p, print "-1" (without quotes). 
  * Otherwise, print n distinct integers p_1, p_2, ..., p_n (1 ≤ p_i ≤ n). If there are multiple possible answers, you can print any of them. 

Example

Input


4
5
1 3 4 5 5
4
1 1 3 4
2
2 2
1
1


Output


1 3 4 5 2 
-1
2 1 
1 

Note

In the first test case of the example answer [1,3,4,5,2] is the only possible answer:

  * q_{1} = p_{1} = 1; 
  * q_{2} = max(p_{1}, p_{2}) = 3; 
  * q_{3} = max(p_{1}, p_{2}, p_{3}) = 4; 
  * q_{4} = max(p_{1}, p_{2}, p_{3}, p_{4}) = 5; 
  * q_{5} = max(p_{1}, p_{2}, p_{3}, p_{4}, p_{5}) = 5. 



It can be proved that there are no answers for the second test case of the example.

Solution (in JAVA):

Solution:
import java.util.*;
public class Solutions {
	static int MAX=Integer.MAX_VALUE;
	static int MIN=Integer.MIN_VALUE;
	static Scanner scr=new Scanner(System.in);
	public static void main(String[] args) {
		int t=read();
		while(t-->0) {
			solve();
		}
	}
	static void solve() {
		int n=read();
		int []a=readIntArray(n);
		int visited[]=new int[n+1];
		int []res=new  int[n];
		int max=0;
		int count=1;
		for(int i=0;i<n;i++) {
			int ele=a[i];
			
			if(ele>max) {
				max=a[i];
				if(visited[ele]==1) {
					println("-1");
					return;
				}
				res[i]=a[i];
				visited[ele]=1;
			}else {
				while(count<max && visited[count]==1) {
					count++;
				}
				if(count>=max) {
					println("-1");
					return;
				}else {
					visited[count]=1;
					res[i]=count;
				}
			}
		}
		printArray(res);
		println();
	}
	static int maxInArray(int a[]) {
		int max=-1;int n=len(a);
		for(int i=0;i<n;i++) {
			max=Math.max(max,a[i]);
		}
		return max;
	}
	static int minInArray(int a[]) {
		int min=MAX;int n=len(a);
		for(int i=0;i<n;i++) {
			min=Math.min(min,a[i]);
		}
		return min;
	}
	static int sumOfArray(int a[]) {
		int sum=0;
		for(int i=0;i<len(a);i++) {
			sum+=a[i];
		}
		return sum;
	}
	static char[] charArray(String s) { 
		return s.toCharArray();
	}
	static int[] sort(int a[]) {
		Arrays.sort(a);
		return a;
	}
	static ArrayList<Integer>sort(ArrayList<Integer>a){
		Collections.sort(a);
		return a;
	}
	static String reverse(String s) {
		String res="";
		for(int i=s.length()-1;i>=0;i--) {
			res+=s.charAt(i);
		}
		return res;
	}static ArrayList<Integer>reverse (ArrayList<Integer>a) {
		ArrayList<Integer>b=new ArrayList<Integer>();
		for(int i=a.size()-1;i>=0;i--) {
			b.add(a.get(i));
		}
		return b;
	}
	static int[] reverse(int a[]) {
		int b[]=new int[a.length];;
		int index=0;
		for(int i=a.length-1;i>=0;i--) {
			b[index]=a[i];
			index++;
		}
		return b;
	}
	static int gcd(int a,int b) {
		if(b==0) {
			return a;
		}
		return gcd(b,a%b);
	}
	static long gcd(long a,long b) {
		if(b==0) {
			return a;
		}
		return gcd(b,a%b);
	}
	static void swap(int a[],int i,int j) {
		int temp=a[i];
		a[i]=a[j];
		a[j]=temp;
	}
	static boolean contains(HashMap<Integer,Integer>hm,int ele) {
		return hm.containsKey(ele);
	}static boolean contains(HashMap<Character,Integer>hm,char ele) {
		return hm.containsKey(ele);
	}static int get(HashMap<Character,Integer>hm,char ele) {
		return hm.get(ele);
	}
	static char[] cha(String s) {
		return s.toCharArray();
	}
	static int len(String s) {
		return s.length();
	}
	static int len(int a[]) {
		return a.length;
	}
	static int len(long a[]) {
		return a.length;
	}
	static long abs(long a) {
		return Math.abs(a);
	}static int abs(int a) {
		return Math.abs(a);
	}
	static long min(long a,long b) {
		return Math.min(a, b);
	}static long max(long a,long b) {
		return Math.max(a, b);
	}
	static void print(int a) {
		System.out.print(a+" ");
	}static void print(long a) {
		System.out.print(a+" ");
	}static void print(String a) {
		System.out.print(a);
	}static void println(int a) {
		System.out.println(a);
	}static void println(long a) {
		System.out.println(a);
	}static void println(String a) {
		System.out.println(a);
	}
	static void println() {
		System.out.println();
	}
	static void println(char []c) {
		for(int i=0;i<c.length;i++) {
			System.out.print(c[i]);
		}
		println();
	}
	static int read() {
		return scr.nextInt();
	}
	static String readS() {
		return scr.next();
	}
	static long readL() {
		return scr.nextLong();
	}
	static int[]readIntArray(int n){
//		int n=read();
		int []a=new int[n];
		for(int i=0;i<n;i++) {
			a[i]=scr.nextInt();
		}
		return a;
	}static long[]readLongArray(int n){
		long []a=new long[n];
		for(int i=0;i<n;i++) {
			a[i]=scr.nextLong();
		}
		return a;
	}
	static void printArray(int a[]) {
		int n=a.length;
		for(int i=0;i<n;i++) {
			print(a[i]);
		}
	}
}
//class pair{
//	int first;
//	int second;
//	pair(int first,int second){
//		this.first=first;
//		this.second=second;
//	}
//}