[Solution] Avoid Squares Please CodeChef Solution

Problem

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 \leq i \lt 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.

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