You are given a permutation $$$a$$$ of length $$$n$$$$$$^{\text{∗}}$$$. You are allowed to do the following operation any number of times (possibly zero):

Choose an index $$$1\le i\le n - 3$$$. Then, swap $$$a_i$$$ with $$$a_{i + 2}$$$, and $$$a_{i + 1}$$$ with $$$a_{i + 3}$$$ simultaneously. In other words, permutation $$$a$$$ will be transformed from $$$[\ldots, a_i, a_{i+1}, a_{i+2}, a_{i+3}, \ldots]$$$ to $$$[\ldots, a_{i+2}, a_{i+3}, a_{i}, a_{i+1}, \ldots]$$$.

Determine the lexicographically smallest permutation$$$^{\text{†}}$$$ that can be obtained by applying the above operation any number of times.

$$$^{\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).

$$$^{\text{†}}$$$An array $$$x$$$ is lexicographically smaller than an array $$$y$$$ of the same size if and only if the following holds:

in the first position where $$$x$$$ and $$$y$$$ differ, the array $$$x$$$ has a smaller element than the corresponding element in $$$y$$$.

Input

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

The first line of each test case contains a single integer $$$n$$$ ($$$4\le n\le 2\cdot 10^5$$$) — the length of permutation $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — the elements of permutation $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output

For each test case, output the lexicographically smallest permutation that can be obtained by applying the above operation any number of times.

Note

In the first test case, an operation can be done on index $$$i = 1$$$, and the permutation will become $$$[1, 2, 3, 4]$$$, which is the lexicographically smallest permutation achievable.

In the second test case, we can do the following sequence of operations:

Do an operation on index $$$i = 2$$$. The permutation becomes $$$[5, 1, 2, 4, 3]$$$.
Do an operation on index $$$i = 1$$$. The permutation becomes $$$[2, 4, 5, 1, 3]$$$.
Do an operation on index $$$i = 2$$$. The permutation becomes $$$[2, 1, 3, 4, 5]$$$.

Quartet Swapping

Examples