You are given an integer N. Construct an array P of size N such that:

P is a permutation of the first N natural numbers, i.e, each integer 1, 2, 3, \ldots N occurs exactly once in P. For example, [1, 3, 2] is a permutation of size 3, but [1, 3, 4] and [2, 1, 2] are not.
P is indivisible. P is said to be indivisible if i does not divide P_{i} for every index 2 ≤ i ≤ N.

It can be proven that under the given constraints, there always exists an indivisible permutation. If there are multiple, you may print any of them.

------ 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 and only line of each test case contains a single integer N, denoting the size of the indivisible permutation you must construct.

------ Output Format ------ 

- For every test case, print a single line containing N space-separated integers. These integers must form an indivisible  permutation.

------ Constraints ------ 

$1 ≤ T ≤ 600$
$2 ≤ N ≤ 10^{5}$
- Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$

----- Sample Input 1 ------ 
4
2
3
4
5
----- Sample Output 1 ------ 
2 1 
1 3 2 
1 3 4 2 
4 5 2 3 1 
----- explanation 1 ------ 
- For the last test case:
- $P_{2} = 5$ is not divisible by $2$
- $P_{3} = 2$ is not divisible by $3$
- $P_{4} = 3$ is not divisible by $4$
- $P_{5} = 1$ is not divisible by $5$
- Since $i$ does not divide $P_{i}$ for every index $2≤ i≤ N$, the permutation is indivisible.

Difficulty: EASY
Tags: Constructive algorithms

Ad-hoc

Starter code:

Solutions:
test = int(input())
for z in range(test):
	n = int(input())
	if n == 1:
		print(1)
		continue
	elif n == 2:
		print(2, 1)
		continue
	arr = [i for i in range(1, n + 1)]
	for i in range(1, n - 1):
		(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
	print(*arr)


t = int(input())
while t > 0:
	n = int(input())
	if n % 2 == 0:
		for i in range(1, n + 1, 2):
			print(i + 1, i, end=' ')
	else:
		print(1, end=' ')
		for i in range(2, n + 1, 2):
			print(i + 1, i, end=' ')
	print()
	t -= 1


t = int(input())
for ni in range(t):
	n = int(input())
	l = [i for i in range(1, n + 1)]
	for i in range(0, n - 1, 2):
		(l[i], l[i + 1]) = (l[i + 1], l[i])
	if n % 2 == 1:
		(l[0], l[-1]) = (l[-1], l[0])
	print(*l)


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


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


for i in range(int(input())):
	n = int(input())
	l = list(range(1, n + 1))
	res = [l[-1]]
	res += l[:-1]
	print(*res)


for _ in range(int(input())):
	n = int(input())
	l = [str(n)]
	m = [str(i) for i in range(1, n)]
	print(*l + m)


for _ in range(int(input())):
	N = int(input())
	A = list(range(2, N + 1)) + [1]
	print(*A)


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


for _ in range(int(input())):
	n = int(input())
	if n % 2 == 0:
		for i in range(1, n + 1, 2):
			print(i + 1, i, end=' ')
	else:
		print(1, end=' ')
		for i in range(2, n + 1, 2):
			print(i + 1, i, end=' ')
	print()


for tc in range(int(input())):
	n = int(input())
	a = []
	for i in range(n):
		if n % 2 == 0:
			if i % 2 == 0:
				a.append(i + 2)
			else:
				a.append(i)
		elif i == 0:
			a.append(1)
		elif i % 2 == 0:
			a.append(i)
		else:
			a.append(i + 2)
	print(*a)


for _ in range(int(input())):
	N = int(input())
	for j in range(1, N + 1):
		if j == N:
			print(1, end=' ')
		else:
			print(j + 1, end=' ')
	print('')


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


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


t = int(input())
for i in range(t):
	n = int(input())
	l = [x for x in range(1, n)]
	l = [n] + l
	print(*l)


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


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


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


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


try:
	for _ in range(int(input())):
		n = int(input())
		l = [i for i in range(n, 0, -1)]
		for i in range(1, len(l) - 1):
			if l[i] % (i + 1) == 0:
				(l[i], l[i + 1]) = (l[i + 1], l[i])
		print(*l)
except:
	pass


from itertools import permutations
casos = int(input())
for i in range(casos):
	n = int(input())
	if n == 2:
		print('2 1')
	else:
		print('1', end=' ')
		for i in range(3, n + 1):
			print(i, end=' ')
		print('2')


for _ in range(int(input())):
	n = int(input())
	l = [i for i in range(n, 0, -1)]
	for i in range(1, n - 1):
		if l[i] % (i + 1) == 0:
			(l[i], l[i + 1]) = (l[i + 1], l[i])
	print(*l)


n = int(input())
for i in range(n):
	x = int(input())
	for p in range(1, x + 1):
		if p == 1:
			print(x, end=' ')
		else:
			print(p - 1, end=' ')
	print('')


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


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


t = input()
for c in range(0, int(t)):
	n = int(input())
	print(n, end=' ')
	for k in range(1, n):
		print(k, end=' ')
	print()


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


tcs = int(input())
while tcs > 0:
	n = int(input())
	el = [None for _ in range(0, n)]
	for index in range(1, n):
		el[index] = index
	el[0] = n
	for x in el:
		print(x, end=' ')
	print()
	tcs -= 1


def main():
	for _ in range(int(input())):
		n = int(input())
		l = list()
		l.append(n)
		for i in range(1, n):
			l.append(i)
		print(' '.join(map(str, l)))
main()


T = int(input())
for i in range(0, T):
	N = int(input())
	arr = []
	for i in range(N):
		arr.append(i + 1)
	for i in range(N):
		arr[i] = i + 2
	arr[N - 1] = 1
	for i in range(N):
		print(arr[i], end=' ')
	print()


T = int(input())
a = []
for i in range(0, T):
	N = int(input())
	for j in range(0, N):
		a += [j + 2]
	a[N - 1] = 1
	print(*a)
	a = []


t = int(input())
for i in range(t):
	n = int(input())
	l = list(range(2, n + 1))
	l.append(1)
	for i in l:
		print(i, end=' ')
	print()


import collections as clts
import math
import heapq
MOD = 10 ** 9 + 7

def gcd(x, y):
	if y == 0:
		return x
	else:
		return gcd(y, x % y)

def lcm(x, y):
	return int(x / gcd(x, y) * y)

def take_input(type='list-int'):
	if type == 'list-int':
		return list(map(int, input().split()))
	elif type == 'list-float':
		return list(map(float, input().split()))
	else:
		return None
for _ in range(int(input())):
	N = int(input())
	res = []
	for i in range(2, N + 1):
		res.append(str(i))
	res.append('1')
	print(' '.join(res))


t = int(input())
for i in range(t):
	n = int(input())
	if n == 2:
		print(2, 1)
	else:
		print(1, end=' ')
		for j in range(3, n + 1):
			print(j, end=' ')
		print(2)


def indivisble(n):
	l = list(range(1, n + 1))
	for i in range(1, n):
		if l[i] % (i + 1) == 0:
			temp = l[i - 1]
			l[i - 1] = l[i]
			l[i] = temp
	print(*l)
	return None
for _ in range(int(input())):
	indivisble(int(input()))


t = int(input())
for i in range(t):
	n = int(input())
	l = [i for i in range(1, n + 1)]
	for i in range(1, len(l)):
		if l[i] % (i + 1) == 0:
			(l[i], l[i - 1]) = (l[i - 1], l[i])
	for i in range(len(l)):
		print(l[i], end=' ')
	print()


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


for _ in range(int(input())):
	x = int(input())
	ll = [0] * x
	ll[0] = x
	for i in range(x - 1):
		ll[i + 1] = i + 1
	print(*ll)


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


T = int(input())
for _ in range(T):
	n = int(input())
	x = 1
	while x < n:
		x += 1
		print(x, end=' ')
	print(1)


for _ in range(int(input())):
	n = int(input())
	lst = [x for x in range(n, 0, -1)]
	for i in range(1, n - 1):
		if lst[i] % (i + 1) == 0:
			(lst[i], lst[i + 1]) = (lst[i + 1], lst[i])
	print(*lst)


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


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


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


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


t = int(input())
for i in range(t):
	l = int(input())
	string = str(l)
	for j in range(1, l):
		string += ' ' + str(j)
	print(string)


for i in range(int(input())):
	x = int(input())
	if x % 2 == 0:
		print(x, end=' ')
		for j in range(2, x):
			if j % 2 == 0:
				print(j + 1, end=' ')
			else:
				print(j - 1, end=' ')
		print(1)
	else:
		print(1, end=' ')
		for j in range(2, x + 1):
			if j % 2 == 0:
				print(j + 1, end=' ')
			else:
				print(j - 1, end=' ')
		print()


t = int(input())
while t:
	t -= 1
	n = int(input())
	li = []
	for i in range(n):
		li.append(str(i))
	li[0] = str(n)
	print(' '.join(li))


for _ in range(int(input())):
	n = int(input())
	print(str(n) + ' ' + ' '.join((str(i) for i in range(1, n))))


for r in range(int(input())):
	n = int(input())
	p = list(range(1, n + 1))
	for i in range(1, n):
		s = 0
		if p[i] % (i + 1) == 0 and i != n - 1:
			s = p[i]
			p[i] = p[i + 1]
			p[i + 1] = s
		elif p[i] % (i + 1) == 0:
			s = p[i]
			p[i] = p[i - 1]
			p[i - 1] = s
	result = ' '.join(map(str, p))
	print(result)


T = int(input())
while T > 0:
	n = int(input())
	if n == 2:
		print(2, 1, end=' ')
	elif (n - 1) % 2 == 0:
		print(1, end=' ')
		for i in range(2, n + 1):
			if i % 2 == 0:
				print(i + 1, end=' ')
			else:
				print(i - 1, end=' ')
	else:
		print(2, 1, end=' ')
		for i in range(3, n + 1):
			if i % 2 != 0:
				print(i + 1, end=' ')
			else:
				print(i - 1, end=' ')
	print('')
	T -= 1


for case in range(int(input())):
	n = int(input())
	target = n
	arr = [str(_ + 1) for _ in range(n)]
	arr = [arr[-1]] + arr[:-1]
	print(' '.join(arr))


t = int(input())
for x in range(t):
	n = int(input())
	l = [x for x in range(1, n + 1)]
	for x in range(0, len(l), 2):
		if len(l) % 2 != 0 and x == len(l) - 1:
			(i, j) = (str(l[len(l) - 1]), str(l[1]))
			l[len(l) - 1] = j
			l[1] = i
			break
		(a, b) = (str(l[x]), str(l[x + 1]))
		l[x] = b
		l[x + 1] = a
	print(' '.join(l))


for _ in range(int(input())):
	n = int(input())
	ans = list()
	for i in range(1, n):
		ans.append(str(i + 1))
	ans.append('1')
	print(' '.join(ans))


t = int(input())
for _ in range(t):
	n = int(input())
	a = []
	for i in range(1, n + 1):
		a.append(i)
	if n == 2:
		print(2, 1)
	else:
		for i in range(1, len(a) - 1):
			(a[i], a[i + 1]) = (a[i + 1], a[i])
		print(*a, sep=' ')