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.*;
import java.io.*;
import java.text.DecimalFormat;
public class Exam {
	public static long mod = (long)Math.pow(10, 9)+7 ;
	public static double epsilon=0.00000000008854;//value of epsilon
	public static InputReader sc = new InputReader(System.in);
	public static PrintWriter pw = new PrintWriter(System.out);
	public static void d(int n,int s,int a[],String ans){
		if(a[0]==1){
			return;
		}
		if(n<=0){
			if(Math.sqrt(s)-(int)Math.sqrt(s)==0)
			{
				a[0]=1;
				pw.println(ans);
			}
			return;
		}
		for(int i=1;i<10;i++){
			d(n-1,s+i*i,a,ans+i);
		}
	}
	public static int gr(int s,int e,int a[][],int k,int dp[][]){
		int t=0;
		if(dp[s][k]!=0)
		return dp[s][k];
		if(s==e&&k==0){
			dp[s][k]=1;
			return 1;
		}
		if(k<=0){
			dp[s][k]=0;
			return 0;
		}
		for(int i=0;i<a[s].length;i++){
			if(a[s][i]==1){
				t+=gr(i,e,a,k-1,dp);
			}
		}
		dp[s][k]=t;
		return t;
	}
	public static int f(int n,int k,int v[],int dp[][]){
		
		if(n==0)
		return 0;
		if(n<0||k<=0)
		return -1;
		if(dp[n][k]!=0){
			return dp[n][k];
		}
		int c=f(n-k,k,v,dp);
		if(c==-1){
			dp[n][k]=f(n, k-1, v, dp);
		}
		else{
			dp[n][k]=Math.max(c+v[k-1],f(n, k-1, v, dp));
		}
		return dp[n][k];
	}
	public static int f1(int n,int v[],int dp[]){
		if(n==0)
		return v[0];
		else if(n==1)
		return Math.max(v[0],v[1]);

		if(dp[n]!=0)
		return dp[n];
		else{
			dp[n]=Math.max(f1(n-2,v,dp)+v[n], f1(n-1,v,dp));
			return dp[n];
		}

	}
	public static double dis(int x,int y,int x1[],int y1[],int x2[],int y2[],int x3[],int y3[]){
		double d1[]=new double [x1.length];
		double d2[]=new double [x2.length];
		Arrays.fill(d2,Long.MAX_VALUE);
		for(int i=0;i<x1.length;i++){
			d1[i]=Math.sqrt(Math.pow(x1[i]-x, 2)+Math.pow(y1[i]-y, 2));
		}
		for(int i=0;i<x2.length;i++){
			for(int j=0;j<x3.length;j++){
				d2[i]=Math.min(Math.sqrt(Math.pow(x2[i]-x3[j], 2)+Math.pow(y2[i]-y3[j], 2)), d2[i]);
			}
		}
		double min=Long.MAX_VALUE;
		for(int i=0;i<x1.length;i++){
			for(int j=0;j<x2.length;j++){
				min=Math.min(d1[i]+d2[j]+Math.sqrt(Math.pow(x1[i]-x2[j], 2)+Math.pow(y1[i]-y2[j], 2)), min);
			}
		}
		return min;
	}
	public static int check(int b,int c,int a[][],int f[]){
		int d=0,in=-1;
		for(int i=0;i<a.length;i++){
			if(i!=f[0]){
				if(b==a[i][0]||b==a[i][1]||b==a[i][2]){
					if(c==a[i][0]||c==a[i][1]||c==a[i][2]){
						in=i;
						f[0]=in;
						break;
					}
				}
			}
		}
		if(in!=-1){
			for(int i=0;i<3;i++){
				if(a[in][i]!=b&&a[in][i]!=c)
				d=a[in][i];
			}
		}
		return d;
	}
	public static long dp(int n,int k,int m,long dp[][],long a[]){
		if(k==0&&n>=-1)
		return 0;
		if(n-m==-1&&k==1){
			dp[n][k]=a[n];
		}
		else if(n-m<0){
			dp[n][k]=0;
		}
		else if(dp[n][k]!=-1)
		return dp[n][k];
		else{
			dp[n][k]=Math.max((long)a[n]+dp(n-m,k-1,m,dp,a), dp(n-1,k,m,dp,a));
		}
		return dp[n][k];
	}
	public static void main(String[] args) {
		// code starts..
		int q=sc.nextInt();
		while(q-->0){
			StringBuilder out=new StringBuilder();
			int n=sc.nextInt();
			int a[]=scanArray(n);
			int h[]=new int[n+1];
			int f=0;
			h[a[0]]=1;
			out.append(a[0]+" ");
			int t=a[0];
			for(int i=1;i<n;i++){
				if(a[i]<a[i-1]){
					f=1;
					break;
				}
				else if(a[i]==a[i-1]){
					while(t>0&&h[t]==1){
						t--;
					}
					if(t<=0){
						f=1;
						break;
					}
					h[t]=1;
					out.append(t+" ");
				}
				else{
					h[a[i]]=1;
					t=a[i];
					out.append(a[i]+" ");
				}
			}
			if(f==1){
				pw.println(-1);
			}
			else{
				pw.println(out);
			}
		}
		// Code ends...
		pw.flush();
		pw.close();
	}
	static class tripletL implements Comparable<tripletL> {
		Long x, y, z;

		tripletL(long x, long y, long z) {
			this.x = x;
			this.y = y;
			this.z = z;
		}

		public int compareTo(tripletL o) {
			int result = x.compareTo(o.x);
			if (result == 0)
				result = y.compareTo(o.y);
			if (result == 0)
				result = z.compareTo(o.z);

			return result;
		}

		public boolean equlas(Object o) {
			if (o instanceof tripletL) {
				tripletL p = (tripletL) o;
				return (x - p.x == 0) && (y - p.y ==0 ) && (z - p.z == 0);
			}
			return false;
		}

		public String toString() {
			return x + " " + y + " " + z;
		}

		public int hashCode() {
			return new Long(x).hashCode() * 31 + new Long(y).hashCode() + new Long(z).hashCode();
		}
	}
	public static String Doubleformate(double a){
		DecimalFormat f =new DecimalFormat("#.00");
		return f.format(a);
	}
 
	public static Comparator<Integer[]> column(int i){
		return 
		new Comparator<Integer[]>() {
			@Override
			public int compare(Integer[] o1, Integer[] o2) {
					Integer quantityOne = o1[i];
				Integer quantityTwo = o2[i];
				return quantityOne.compareTo(quantityTwo);
			}
		};
	}
	public static Comparator<Integer[]> pair(){
		return 
		new Comparator<Integer[]>() {
			@Override
			public int compare(Integer[] o1, Integer[] o2) {
				int result=o1[0].compareTo(o2[0]);
				if(result==0)
				result=o1[1].compareTo(o2[1]);
				return result;
			}
		};
	}
	public static Comparator<Integer[]> Triplet(){
		return 
		new Comparator<Integer[]>() {
			@Override
			public int compare(Integer[] o1, Integer[] o2) {
			
					for(int i=0;i<3;i++){
						for(int j=i+1;j<3;j++){
							for(int k=0;k<3;k++){
								for(int p=k+1;p<3;p++){
									if((o1[i]==o2[k]&&o1[j]==o2[p])||(o1[j]==o2[k]&&o1[i]==o2[p])){

									}
								}
							}
						}
					}
					int result=o1[0].compareTo(o2[0]);
					if(result==0)
					result=o1[1].compareTo(o2[1]);
					if(result==0)
					result=o1[2].compareTo(o2[2]);
					return result;
			}
		};
	}
	
	
	public static String reverseString(String s){
		StringBuilder input1 = new StringBuilder(); 
        input1.append(s);  
		input1 = input1.reverse();
		return input1.toString();
	}
	public static int[] scanArray(int n){
		int a[]=new int [n];
		for(int i=0;i<n;i++)
		a[i]=sc.nextInt();
 
		return a;
	}
	public static long[] scanLongArray(int n){
		long a[]=new long [n];
		for(int i=0;i<n;i++)
		a[i]=sc.nextLong();
 
		return a;
	}
	public static String [] scanStrings(int n){
		String a[]=new String [n];
		for(int i=0;i<n;i++)
		a[i]=sc.nextLine();
 
		return a;
	}
	static class InputReader {
 
		private final InputStream stream;
		private final byte[] buf = new byte[8192];
		private int curChar, snumChars;
		private SpaceCharFilter filter;
 
		public InputReader(InputStream stream) {
			this.stream = stream;
		}
 
		public int snext() {
			if (snumChars == -1)
				throw new InputMismatchException();
			if (curChar >= snumChars) {
				curChar = 0;
				try {
					snumChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (snumChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}
 
		public int nextInt() {
			int c = snext();
			while (isSpaceChar(c)) {
				c = snext();
			}
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = snext();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = snext();
			} while (!isSpaceChar(c));
			return res * sgn;
		}
 
		public long nextLong() {
			int c = snext();
			while (isSpaceChar(c)) {
				c = snext();
			}
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = snext();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = snext();
			} while (!isSpaceChar(c));
			return res * sgn;
		}
 
		public int[] nextIntArray(int n) {
			int a[] = new int[n];
			for (int i = 0; i < n; i++) {
				a[i] = nextInt();
			}
			return a;
		}
 
		public String readString() {
			int c = snext();
			while (isSpaceChar(c)) {
				c = snext();
			}
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = snext();
			} while (!isSpaceChar(c));
			return res.toString();
		}
 
		public String nextLine() {
			int c = snext();
			while (isSpaceChar(c))
				c = snext();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = snext();
			} while (!isEndOfLine(c));
			return res.toString();
		}
 
		public boolean isSpaceChar(int c) {
			if (filter != null)
				return filter.isSpaceChar(c);
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
 
		private boolean isEndOfLine(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}
 
		public interface SpaceCharFilter {
			public boolean isSpaceChar(int ch);
		}
	}
 
}