Avoid Squares Please

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 - The first line of input con