Problem Statement

You are given a sequence $A = (A_1, A_2, \ldots, A_N)$ of length $N$. Each element is either an integer between $1$ and $N$ (inclusive) or $-1$.

Snuke has decided to create a new sequence using this sequence $A$.

First, replace all $-1$s in this sequence $A$ with integers between $1$ and $N$ (inclusive).

Next, create a sequence $B = (B_1, B_2, \ldots, B_N)$ of length $N$ according to the following formula:

• $B_i=A_{A_i}$

Find the lexicographically smallest possible sequence $B$.

You are given $T$ test cases. Solve each of them.

What is the lexicographical order of sequences? A sequence $C = (C_1,C_2,\ldots,C_N)$ is lexicographically smaller than a sequence $D = (D_1,D_2,\ldots,D_N)$ if and only if there exists an integer $1 \leq i \leq N$ such that both of the following hold: $(C_1,C_2,\ldots,C_{i-1}) = (D_1,D_2,\ldots,D_{i-1})$ $C_i$ is (numerically) smaller than $D_i$.

Constraints

• $1 \le T \le 10^5$
• $1 \le N \le 5 \times 10^5$
• $1 \le A_i \le N$ or $A_i = -1$.
• The sum of $N$ over all test cases is at most $5\times 10^5$.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

T
case_1
case_2
\vdots
case_T

Each case is given in the following format:

N
A_1 A_2 \dots A_N

Output

For each test case, output the lexicographically smallest possible sequence $B$, separated by newlines.