You are given an integer N.

Print a permutation P of $[1,2, \ldots, N]$ such that the following condition holds:
For any index i\ (1 ≤ $i < N), P_{i} \times P_{i+1}$ is not a perfect square.

If there are multiple correct answers, you may print any of them.

Note: A permutation of $[1, 2, \ldots, N]$ is a rearrangement of those numbers.

------ Input Format ------

• The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
• The first line of each test case contains an integer N - the length of the required permutation.

------ Output Format ------

For each test case, print N space-separated integers representing the valid permutation on a single line.

If there are multiple correct answers, you may print any of them.

------ Constraints ------

$1 ≤ T ≤ 500$
$2 ≤ N ≤ 500$

----- Sample Input 1 ------
3
2
3
4

----- Sample Output 1 ------
2 1
3 1 2
4 2 3 1

----- explanation 1 ------
Test case $1$: $2\times 1 = 2$ is not a perfect square. Note that $[1, 2]$ is also a valid answer for this case, and will be accepted.

Test case $2$: $3\times 1 = 3$ and $1\times 2 = 2$ are not perfect squares.

Test case $3$: $4\times 2 = 8, 2\times 3 = 6, 3\times 1 = 3$ are all not perfect squares.

见题面

见题面