Avoid Squares Please Codechef Solution

Problem

You are given an integer $N$.

Print a permutation $P$ of $[1,2,\dots ,N]$ such that the following condition holds:

• For any index $i(1\le i<N)$, P_i \times P_{i+1}Pi​×Pi+1​ is not a perfect square.

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

Note: A permutation of $[1,2,\dots ,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

Sample 1:

3
2
3
4

2 1
3 1 2
4 2 3 1

Explanation:

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.