Problem: Vasya has written some permutation p_1, p_2, …, p_n of integers from 1 to n, so for all 1 ≤ i ≤ n it is true that 1 ≤ p_i ≤ n and all p_1, p_2, …, p_n are different. After that he wrote n numbers next_1, next_2, …, next_n. The number next_i is equal to the minimal index i < j ≤ n, such that p_j > p_i. If there is no such j let's let's define as next_i = n + 1.

In the evening Vasya went home from school and due to rain, his notebook got wet. Now it is impossible to read some written numbers. Permutation and some values next_i are completely lost! If for some i the value next_i is lost, let's say that next_i = -1.

You are given numbers next_1, next_2, …, next_n (maybe some of them are equal to -1). Help Vasya to find such permutation p_1, p_2, …, p_n of integers from 1 to n, that he can write it to the notebook and all numbers next_i, which are not equal to -1, will be correct. 

Input

The first line contains one integer t — the number of test cases (1 ≤ t ≤ 100 000).

Next 2 ⋅ t lines contains the description of test cases,two lines for each. The first line contains one integer n — the length of the permutation, written by Vasya (1 ≤ n ≤ 500 000). The second line contains n integers next_1, next_2, …, next_n, separated by spaces (next_i = -1 or i < next_i ≤ n + 1).

It is guaranteed, that the sum of n in all test cases doesn't exceed 500 000.

In hacks you can only use one test case, so T = 1.

Output

Print T lines, in i-th of them answer to the i-th test case.

If there is no such permutations p_1, p_2, …, p_n of integers from 1 to n, that Vasya could write, print the only number -1.

In the other case print n different integers p_1, p_2, …, p_n, separated by spaces (1 ≤ p_i ≤ n). All defined values of next_i which are not equal to -1 should be computed correctly p_1, p_2, …, p_n using defenition given in the statement of the problem. If there exists more than one solution you can find any of them.

Example

Input


6
3
2 3 4
2
3 3
3
-1 -1 -1
3
3 4 -1
1
2
4
4 -1 4 5


Output


1 2 3
2 1
2 1 3
-1
1
3 2 1 4

Note

In the first test case for permutation p = [1, 2, 3] Vasya should write next = [2, 3, 4], because each number in permutation is less than next. It's easy to see, that it is the only satisfying permutation.

In the third test case, any permutation can be the answer because all numbers next_i are lost.

In the fourth test case, there is no satisfying permutation, so the answer is -1.

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;

public class Main {

    static int N;
    static int[] B;

    public static void main(String[] args) {
        FastScanner sc = new FastScanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        int T = sc.nextInt();
        for (int i = 0; i < T; i++) {
            N = sc.nextInt();
            B = sc.nextIntArray(N, -1);
            int[] ans = solve();
            if( ans == null ) {
                pw.println(-1);
            } else {
                writeSingleLine(ans, pw);
            }
        }
        pw.flush();
    }

    static int[] solve() {
        List<Edge> edges = new ArrayList<>();
        ArrayDeque<Edge> stack = new ArrayDeque<>();
        for (int a = 0; a < N; a++) {
            while(!stack.isEmpty() && stack.peek().b == a ) {
                stack.poll();
            }

            int b = B[a];
            if( b == -2 ) { // -1 -1
                // almighty
                if( !stack.isEmpty() ) {
                    Edge prev = stack.peek();
                    edges.add( new Edge(a, prev.a) );
                }

            } else {
                if( b <= a ) return null;

                if( !stack.isEmpty() ) {
                    Edge prev = stack.peek();
                    if( prev.b < b ) return null;

                    Edge curr = new Edge(a, b);
                    stack.addFirst( curr );
                    edges.add(curr);
                    Edge toPrev = new Edge(a, prev.a);
                    edges.add( toPrev );

                } else {
                    Edge curr = new Edge(a, b);
                    stack.addFirst( curr );
                    edges.add(curr);
                }
            }
        }

        // remove N
        List<Edge> edges2 = new ArrayList<>();
        for (Edge edge : edges) {
            if( edge.b != N ) edges2.add( edge );
        }

        int[][] G = adjD(N, edges2);
        int[] topo = khan(N, G);
        if( topo == null ) return null;

        // debug(topo);
        int[] p = new int[N];
        for (int i = 0; i < N; i++) {
            int a = topo[i];
            p[a] = i+1;
        }
        return p;
    }

    static int[] khan(int V, int[][] G) {
        int[] deg = new int[V];
        for (int[] tos : G) {
            for (int to : tos) {
                deg[to]++;
            }
        }

        int[] q = new int[V];
        int a = 0, b = 0;
        for (int v = 0; v < V; v++) {
            if( deg[v] == 0 ) q[b++] = v;
        }

        int[] ret = new int[V];
        int idx = 0;
        while( a != b ) {
            int v = q[a++];
            ret[idx++] = v;
            for (int to : G[v]) {
                deg[to]--;
                if( deg[to] == 0 ) {
                    q[b++] = to;
                }
            }
        }

        for (int v = 0; v < V; v++) {
            if( deg[v] != 0 ) return null;
        }
        return ret;
    }

    static int[][] adjD(int n, List<Edge> es) {
        int[][] adj = new int[n][];
        int[] cnt = new int[n];

        for (Edge e : es) {
            cnt[e.a]++;
        }
        for (int i = 0; i < n; i++) {
            adj[i] = new int[cnt[i]];
        }
        for (Edge e : es) {
            adj[e.a][--cnt[e.a]] = e.b;
        }
        return adj;
    }

    // a -> b
    static class Edge {
        int a, b;

        public Edge(int a, int b) {
            this.a = a;
            this.b = b;
        }

        public String toString() {
            return "(" + a + "," + b + ")";
        }
    }

    @SuppressWarnings("unused")
    static class FastScanner {
        private BufferedReader reader;
        private StringTokenizer tokenizer;

        FastScanner(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
            tokenizer = null;
        }

        String next() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        String nextLine() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    return reader.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken("\n");
        }

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

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

        int[] nextIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = nextInt();
            return a;
        }

        int[] nextIntArray(int n, int delta) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = nextInt() + delta;
            return a;
        }

        long[] nextLongArray(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++) a[i] = nextLong();
            return a;
        }
    }

    static void writeLines(int[] as) {
        PrintWriter pw = new PrintWriter(System.out);
        for (int a : as) pw.println(a);
        pw.flush();
    }

    static void writeLines(long[] as) {
        PrintWriter pw = new PrintWriter(System.out);
        for (long a : as) pw.println(a);
        pw.flush();
    }

    static void writeSingleLine(int[] as, PrintWriter pw) {
        for (int i = 0; i < as.length; i++) {
            if (i != 0) pw.print(" ");
            pw.print(as[i]);
        }
        pw.println();
    }

    static int max(int... as) {
        int max = Integer.MIN_VALUE;
        for (int a : as) max = Math.max(a, max);
        return max;
    }

    static int min(int... as) {
        int min = Integer.MAX_VALUE;
        for (int a : as) min = Math.min(a, min);
        return min;
    }

    static void debug(Object... args) {
        StringJoiner j = new StringJoiner(" ");
        for (Object arg : args) {
            if (arg == null) j.add("null");
            else if (arg instanceof int[]) j.add(Arrays.toString((int[]) arg));
            else if (arg instanceof long[]) j.add(Arrays.toString((long[]) arg));
            else if (arg instanceof double[]) j.add(Arrays.toString((double[]) arg));
            else if (arg instanceof Object[]) j.add(Arrays.toString((Object[]) arg));
            else j.add(arg.toString());
        }
        System.err.println(j.toString());
    }

    static void printSingleLine(int[] array) {
        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < array.length; i++) {
            if (i != 0) pw.print(" ");
            pw.print(array[i]);
        }
        pw.println();
        pw.flush();
    }

    static int lowerBound(int[] array, int value) {
        int lo = 0, hi = array.length, mid;
        while (lo < hi) {
            mid = (hi + lo) / 2;
            if (array[mid] < value) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }

    static int upperBound(int[] array, int value) {
        int lo = 0, hi = array.length, mid;
        while (lo < hi) {
            mid = (hi + lo) / 2;
            if (array[mid] <= value) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }
}