Given an integer N, find a permutation P = P_{1}, P_{2}, \ldots, P_{N} of length N that satisfies the following two conditions:
P_{i} \neq i (1 ≤ i ≤ N);
Consider the set which contains P_{i} \% i for all 1 ≤ i ≤ N. This set should have the minimum number of distinct integers possible, over all permutations P.

Note that a permutation of length N is an array containing every integer from 1 to N exactly once.

------ Input Format ------ 

- The first line will contain T, number of test cases. Then the test cases follow.
- Each test case consists of a single line of input, an integer N, the length of the required permutation.
   
------ Output Format ------ 

For each test case, output on a new line, N space-separated integers, denoting the permutation P of length N satisfying the above conditions.

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

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

------ subtasks ------ 

Subtask 1 (10 points): $1 ≤ M ≤ 10$
Subtask 2 (20 points): The sum of $N$ across all test cases won't exceed $20$.
Subtask 3 (70 points): No further constraints.

----- Sample Input 1 ------ 
2
2
3

----- Sample Output 1 ------ 
2 1
2 3 1
----- explanation 1 ------ 
Test case $1$: The possible permutations of length $2$ are $[1,2]$ and $[2,1]$. The only permutation that satisfies the conditions is $[2,1]$. The values $P_{i}$ $\%$ $i$ are $[2\%1, 1\%2] = [0, 1]$.  
Thus there are $2$ distinct values of $P_{i}$ $\%$ $i$, which is the minimum possible.

Test case $2$: There are $6$ possible permutations of length $3$ out of which $[2,3,1]$ satisfies the above conditions. The values $P_{i}$ $\%$ $i$ are $[2\%1, 3\%2, 1\%3] = [0, 1, 1]$.  
Thus there are $2$ distinct values of $P_{i}$ $\%$ $i$, which is the minimum possible.

Difficulty: EASY
Tags: Constructive algorithms

Starter code:

Solutions:
T = int(input())
for i in range(T):
	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 = []
	for j in range(2, N + 1):
		l.append(j)
	l.append(1)
	for j in l:
		print(j, end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	print(*list(range(2, n + 1)), 1)


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


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


class Mode:

	def __init__(self, n):
		self.n = n

	def Solution(self):
		print(*list(range(2, self.n + 1)), 1)

def main():
	for _ in range(int(input())):
		n = int(input())
		ans = Mode(n)
		ans.Solution()
main()


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


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


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


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


t = int(input())
for i in range(t):
	n = int(input())
	res = [k % n + 1 for k in range(1, n + 1)]
	print(' '.join(map(str, res)))


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


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

def user_input():
	t = int(input())
	for _ in range(t):
		n = int(input())
		solve(n)
		print()
user_input()


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


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


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


for i in range(int(input())):
	n = int(input())
	if 2 <= n <= 10 ** 5:
		for i in range(n - 1):
			print(2 + i, end=' ')
		print(1)


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


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


for t in range(int(input())):
	n = int(input())
	print(*list(range(2, n + 1)), 1)


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


for t in range(int(input())):
	a = int(input())
	print(*list(range(2, a + 1)), 1)


t = int(input())
for i in range(t):
	n = int(input())
	res = []
	for j in range(2, n + 1):
		res.append(j)
	res.append(1)
	for j in range(len(res)):
		print(res[j], end=' ')
	print()


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


T = int(input())
for i in range(T):
	N = int(input())
	p = []
	for k in range(N):
		if k != N - 1:
			c = k + 2
			p.append(c)
		else:
			l = 1
			p.append(l)
	for s in p:
		print(s, end=' ')
	print()


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


t = int(input())
for tc in range(t):
	x = int(input())
	for k in range(2, x + 1):
		print(k, end=' ')
	print(1)


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


t = int(input())
for i in range(0, t):
	n = int(input())
	print(*list(range(2, n + 1)), 1)


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


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


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


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


from itertools import permutations
for _ in range(int(input())):
	n = int(input())
	lt = list(range(1, n + 1))
	for x in lt[1:n]:
		print(x, end=' ')
	print(lt[0])


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


t = int(input())
for i in range(t):
	n = int(input())
	lst = [i for i in range(1, n + 1)]
	sp = 0
	ep = len(lst) - 1
	while ep > 0:
		(lst[sp], lst[ep]) = (lst[ep], lst[sp])
		ep -= 1
	for i in lst:
		print(i, end=' ')
	print()


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


testcases = int(input())
for eachcase in range(testcases):
	length = int(input())
	ans = [nums for nums in range(2, length + 1)]
	ans.append(1)
	print(*ans)


for t in range(int(input())):
	n = int(input())
	s = '2 '
	if n > 2:
		for i in range(3, n + 1):
			i = str(i)
			s += i
			s += ' '
	s += '1'
	print(s)


for t in range(int(input())):
	n = int(input())
	print(' '.join(map(str, range(2, n + 1))) + ' 1')


for i in range(int(input())):
	x = int(input())
	z = 2
	while z < x + 1:
		print(z, end=' ')
		z += 1
	print(1)


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


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


for _ in range(int(input())):
	x = int(input())
	print(*list(range(2, x + 1)), 1)


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