Goodman

S'all good, man.

• James McGill, Better Call Saul

Saul Goodman is the best lawyer in the world. He believes that until proven guilty, every man, woman, and child in this country is innocent. However, one client of Saul is not so innocent.

Saul needs to build a solid story for his defense. There were $n$ events, numbered from $1$ to $n$. Saul needs to come up with an order $q_1, q_2, \ldots, q_n$, in which these events happened. His client, however, has a poor memory! If Saul tells him to remember permutation $(q_1, q_2, \ldots, q_n)$ of events, he will remember permutation $(p_{q_1}, p_{q_2}, \ldots, p_{q_n})$, where $(p_1, p_2, \ldots, p_n)$ is some (fixed) permutation of integers from $1$ to $n$.

Saul wants their permutations to be as consistent as possible: he wants to maximize the value of $LCS((q_1, q_2, \ldots, q_n), (p_{q_1}, p_{q_2}, \ldots, p_{q_n}))$. Help him to find permutation $(q_1, q_2, \ldots, q_n)$ which maximizes this value! If there are many such permutations, find any of them.

Here $LCS(a, b)$ denotes the length of the longest common subsequence of sequences $a$ and $b$. For example, $LCS((1, 3, 4, 2, 5), (3, 1, 2, 4, 5)) = 3$, and one of the common subsequences of length $3$ is $(1, 2, 5)$.

Input data

The first line contains a single integer $t$ ($1 \le t \le 10^5$) - the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 10^6$) - the length of the permutation.

The second line of each test case contains $n$ integers $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$, all $p_i$ are distinct) - the elements of the permutation.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

Output data

For each test case, output $n$ integers $q_1, q_2, \ldots, q_n$ ($1 \le q_i \le n$, all $q_i$ are distinct) ~--- any permutation of integers from $1$ to $n$, which maximizes the value of $LCS((q_1, q_2, \ldots, q_n), (p_{q_1}, p_{q_2}, \ldots, p_{q_n}))$.

Example

stdin

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

stdout

1 2 3 4 
1 6 2 5 3 4 

Explanation

In the first test case, for $q = (1, 2, 3, 4)$, we have $LCS((1, 2, 3, 4), (p_1, p_2, p_3, p_4))$ = $LCS((1, 2, 3, 4), (1, 2, 3, 4)) = 4$.

In the second test case, for $q = (1, 6, 2, 5, 3, 4)$, we have:

$LCS((1, 6, 2, 5, 3, 4), (p_1, p_6, p_2, p_5, p_3, p_4))$ = $LCS((1, 6, 2, 5, 3, 4), (6, 1, 5, 2, 4, 3))$ = 3KaTeX parse error: Can't use function '$' in math mode at position 40: …nces of length $̲3 is $(1, 2, 3)$.