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.

Source: codechef | Difficulty: EASY
Tags: Mathematics


Solutions:
t = int(input())
for i in range(t):
	n = int(input())
	for x in range(n):
		print(x + 1, end='')
		print(' ', end='')
	print('')


for i in range(int(input())):
	for i in range(int(input())):
		print(i + 1, end=' ')
	print()


for t in range(int(input())):
	n = int(input())
	b = []
	for i in range(1, n + 1):
		print(i, end=' ')
	print('\n')


from itertools import permutations
t = int(input())
for i in range(t):
	n = int(input())
	lst = list(range(1, n + 1))
	perm = permutations(lst)
	flag = 1
	for p in perm:
		for j in range(n - 1):
			if type((p[j] * p[j + 1]) ** 0.5) == int:
				flag = 0
				break
		if flag == 1:
			res = []
			for k in p:
				res.append(str(k))
			print(' '.join(res))
			break


import math
for i in range(int(input())):
	x = int(input())
	y = []
	for j in range(1, x + 1):
		if j == 1:
			continue
		z = j * (j - 1)
		root = math.sqrt(z)
		if int(root + 0.5) ** 2 != z:
			y.append(j)
			y.append(j - 1)
	a = [*set(y)]
	for m in range(len(a)):
		print(a[m], end=' ')
	print(' ')


for i in range(int(input())):
	print(*list(range(1, int(input()) + 1)))


t = int(input())
for i in range(t):
	a = int(input())
	for i in range(1, a + 1):
		print(i, end=' ')
	print('\n')


T = int(input())
for _ in range(T):
	N = int(input())
	print(*[i for i in range(1, N + 1)])


t = int(input())
for i in range(t):
	n = int(input())
	for i in range(n, 0, -1):
		print(i, end=' ')
	print('\n')


t = int(input())
for _ in range(t):
	n = int(input())
	for i in range(1, n + 1):
		print(i, end=' ')
	print()


for _ in range(int(input())):
	a = int(input())
	for i in range(1, a + 1):
		print(i, end=' ')
	print('')


for _ in range(int(input())):
	k = [int(x) for x in range(1, int(input()) + 1)]
	print(*k)


for _ in range(int(input())):
	n = int(input())
	ans = []
	for i in range(1, n + 1):
		ans.append(i)
	print(*ans)


for _ in range(int(input())):
	ps = [i * i for i in range(1, 501)]
	n = int(input())
	p = [i for i in range(n, 0, -1)]
	for i in range(len(p) - 1):
		if p[i] * p[i + 1] in ps:
			(p[i], p[i + 1]) = (p[i + 1], p[i])
	for j in p:
		print(j, end=' ')
	print('\n')


T = int(input())
for i in range(T):
	N = int(input())
	for i in range(1, N + 1):
		print(i, end=' ')
	print('\n')


for _ in range(int(input())):
	x = int(input())
	l = []
	for i in range(1, x + 1):
		a = str(i)
		l.append(a)
	print(' '.join(l))


for _ in range(int(input())):
	x = int(input())
	list1 = []
	for i in range(1, x + 1):
		list1.append(str(i))
	print(' '.join(list1))


for i in range(int(input())):
	res = []
	for i in range(1, int(input()) + 1):
		res.append(str(i))
	print(' '.join(res))


for i in range(int(input())):
	n = int(input())
	l = []
	for j in range(1, n + 1):
		l.append(j)
	print(*l)


n = int(input())
for i in range(0, n):
	c = int(input())
	for j in range(1, c + 1):
		print(j, end=' ')
	print()


import math
import random
for _ in range(int(input())):
	a = int(input())
	list1 = []
	j = 0
	for i in range(1, a + 1):
		list1.append(i)
	list1 = list1
	for i in list1:
		root = math.sqrt(list1[j] * list1[j + 1])
		if list1[j] * list1[j + 1] != int(root + 0.5) ** 2:
			print(' '.join((str(x) for x in list1)))
			break
		else:
			random.shuffle(list1)


for i in range(int(input())):
	n = int(input())
	for x in range(n, 0, -1):
		print(x, end=' ')
	print()


for t in range(int(input())):
	n = int(input())
	lis = []
	while n > 1:
		for i in range(1, n + 1):
			lis.append(n)
			n = n - 1
	for i in lis:
		print(i, end=' ')
	print(' ')


for i in range(int(input())):
	n = int(input())
	u = []
	for i in range(1, n + 1):
		u.append(n)
		n -= 1
	for i in u:
		print(i, end=' ')
	print()


for i in range(int(input())):
	n = int(input())
	for j in range(1, n + 1):
		print(j, end=' ')
	print()


t = int(input())
for i in range(t):
	n = int(input())
	l = set()
	for i in range(1, n + 1):
		print(i, end=' ')
	print()


T = int(input())
for i in range(T):
	N = int(input())
	for j in range(N):
		print(j + 1, end=' ')
	print()


for i in range(int(input())):
	a = int(input())
	for j in range(a):
		print(j + 1, end=' ')
	print()


k = int(input())
for c in range(k):
	p = int(input())
	m = []
	for l in range(1, p + 1):
		m.append(p)
		p -= 1
	for l in m:
		print(l, end=' ')
	print()


t = int(input())
for tc in range(t):
	n = int(input())
	l = []
	for j in range(1, n + 1):
		l.append(n)
		n -= 1
	for j in l:
		print(j, end=' ')
	print()


for i in range(int(input())):
	n = int(input())
	a = str(n)
	while n > 1:
		b = n * (n - 1)
		c = b ** (1 / 2)
		if b / c != 0:
			a = a + ' ' + str(n - 1)
		n = n - 1
	print(a)


t = int(input())
for i in range(t):
	n = int(input())
	p = []
	for i in range(1, n + 1):
		p.append(str(i))
	print(' '.join(p))


t = int(input())
for I in range(t):
	arr = []
	n = int(input())
	for i1 in range(1, n + 1):
		arr.append(i1)
	for m in arr:
		print(m, end=' ')
	print('\n')


t = int(input())
for i in range(t):
	n = int(input())
	val = []
	for m in range(1, n + 1):
		val.append(m)
	for m in val:
		print(m, end=' ')
	print('\n')