Those cling-on troubles that ride my stride — cough up the fee, or step aside.— SHUN, TAKE IT AWAY

For a permutation$^{\text{∗}}$ $r$ of length $m$, we call an index $i$ ($1\le i\le m$) ugly if and only if $i=\max(\{r_1,r_2,\ldots,r_i\})$.

Simons has a permutation $p$ of length $n$, and he can perform the following operation on $p$ at most once:

• Choose two indices $i$ and $j$ ($1\le i\ne j\le n$), then swap $p_i$ and $p_j$.

Find a permutation $q$ that can be obtained from $p$ by performing the above operation at most once, such that the number of ugly indices in $q$ is minimized.

$^{\text{∗}}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). The description of the test cases follows.

The first line contains an integer $n$ ($1\le n\le 500$) — the length of $p$.

The second line contains $n$ integers $p_1,p_2,\ldots,p_n$ ($1\le p_i\le n$, all $p_i$-s are distinct) — the elements of $p$.

Output

For each test case, print $n$ integers $q_1,q_2,\ldots,q_n$ — the permutation you found.

If there are multiple possible permutations, you may output any.

Note

In the first test case, Simons can obtain only two possible permutations: $[1,2]$ and $[2,1]$.

• For permutation $[1,2]$, we can see $1=\max(\{1\})$ and $2=\max(\{1,2\})$. So there are two ugly indices.
• For permutation $[2,1]$, we can see $1\ne\max(\{2\})$ and $2=\max(\{2,1\})$. So there is only one ugly index.

Thus, permutation $[2,1]$ has the minimum count of ugly indices.

In the second test case, Simons can obtain permutation $[2,4,1,3]$ by choosing indices $2$ and $4$ to swap. There is only one ugly index in the permutation:

• $1\ne \max(\{2\})$, so index $1$ is not ugly;
• $2\ne \max(\{2,4\})$, so index $2$ is not ugly;
• $3\ne \max(\{2,4,1\})$, so index $3$ is not ugly;
• $4=\max(\{2,4,1,3\})$, so index $4$ is ugly.

In the third test case, note that Simons does not perform the operation.

Samples

5
2
1 2
4
2 3 1 4
5
3 2 4 5 1
1
1
8
4 1 3 2 6 7 8 5

2 1
2 4 1 3
3 2 4 5 1
1
4 1 3 8 6 7 2 5