# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* Satyam

*Takuki Kurokawa, Utkarsh Gupta*

**Testers:***Nishank Suresh*

**Editorialist:**# DIFFICULTY:

960

# PREREQUISITES:

None

# PROBLEM:

Given N, find a permutation of \{1, 2, 3, \ldots, N\} such that the product of any two adjacent elements is not a square.

# EXPLANATION:

The solution is simple: print 1 \ 2 \ 3 \ \ldots \ N.

## Proof

In the given permutation, products are of the form i\times (i+1) for some positive integer.

Such a product can never be a square, because:

- i^2 \lt i\times (i+1) \lt (i+1)^2
- There is no perfect square between i^2 and (i+1)^2 since they’re already adjacent squares.

# TIME COMPLEXITY

\mathcal{O}(N) per test case.

# CODE:

## Code (Python)

```
for _ in range(int(input())):
print(*range(1, int(input())+1))
```