You are given a positive integer $n$.

The weight of a permutation $p_1, p_2, \ldots, p_n$ is the number of indices $1\le i\le n$ such that $i$ divides $p_i$. Find a permutation $p_1,p_2,\dots, p_n$ with the minimum possible weight (among all permutations of length $n$).

A permutation is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array) and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 10^4$). The description of the test cases follows.

The only line of each test case contains a single integer $n$ ($1 \leq n \leq 10^5$) — the length of permutation.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.


-----Output-----

For each test case, print a line containing $n$ integers $p_1, p_2,\dots, p_n$ so that the permutation $p$ has the minimum possible weight.

If there are several possible answers, you can print any of them.


-----Examples-----

Input
2
1
4
Output
1
2 1 4 3


-----Note-----

In the first test case, the only valid permutation is $p=[1]$. Its weight is $1$.

In the second test case, one possible answer is the permutation $p=[2,1,4,3]$. One can check that $1$ divides $p_1$ and $i$ does not divide $p_i$ for $i=2,3,4$, so the weight of this permutation is $1$. It is impossible to find a permutation of length $4$ with a strictly smaller weight.

Difficulty: EASY
Tags: Constructive algorithms

Starter code:

Solutions:
import sys
inp = sys.stdin.readline
for _ in range(int(inp())):
	n = int(inp())
	print(' '.join([str(i + 1) if i < n else '1' for i in range(1, n + 1)]))


import fileinput

def computePermutation(n):
	ans = [str(n)] + [str(x) for x in range(1, n)]
	print(' '.join(ans))
cases = 0
for line in fileinput.input():
	if cases == 0:
		cases = int(line.strip())
	else:
		n = int(line.strip())
		computePermutation(n)
		cases -= 1
		if cases == 0:
			break


test_case = int(input())
nums = []
for k in range(test_case):
	num = int(input())
	nums.append(num)
for k in range(test_case):
	ans = []
	if nums[k] == 1:
		print(1)
	else:
		for i in range(1, nums[k]):
			ans.append(i + 1)
		ans.append(1)
		print(' '.join(map(str, ans)))


n = int(input())
x = []
for i in range(n):
	x.append(int(input()))
for elements in x:
	if elements == 1:
		print('1')
	elif elements > 1:
		if elements % 2 == 0:
			y = '2 1'
			for k in range(3, elements + 1):
				if k % 2 == 1:
					y = y + f' {k + 1}'
				else:
					y = y + f' {k - 1}'
		else:
			y = '1'
			for g in range(2, elements + 1):
				if g % 2 == 0:
					y = y + f' {g + 1}'
				else:
					y = y + f' {g - 1}'
		print(y)


import sys, math
lines = [line.rstrip() for line in sys.stdin]
n_cases = int(lines[0])
for i in range(n_cases):
	l = lines[i + 1]
	vals = list(range(2, int(l) + 1))
	vals.append(1)
	vals = [str(x) for x in vals]
	out = ' '.join(vals)
	print(out)


n = int(input())
tLst = []
for i in range(0, n):
	x = int(input())
	tLst.append(x)
for i in range(0, n):
	pLst = [tLst[i]]
	for i in range(1, tLst[i]):
		pLst.append(i)
	s_pLst = [str(i) for i in pLst]
	s = ' '.join(s_pLst)
	print(s)


def ans(n):
	p = []
	p.append(n)
	for i in range(n - 1):
		p.append(i + 1)
	return p
t = int(input())
r = []
for i in range(t):
	n = int(input())
	c = ans(n)
	r.append(c)
for i in range(t):
	print(' '.join(map(str, r[i])))


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


n = int(input())
res = []
for i in range(n):
	cur = int(input())
	cur_ans = []
	for j in range(1, (cur - cur % 2) // 2 + 1):
		cur_ans.append(j * 2)
		cur_ans.append(j * 2 - 1)
	if cur % 2 != 0:
		if len(cur_ans) > 0:
			cur_ans[0] = cur
			cur_ans.append(2)
		else:
			cur_ans.append(cur)
	res.append(cur_ans)
for i in res:
	print(' '.join(map(str, i)))


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


import sys

def solve(n):
	if n == 1:
		print('1')
		return
	data = [i + 1 if i % 2 != 0 else i - 1 for i in range(1, n + 1 if n % 2 == 0 else n)]
	if len(data) < n:
		data[-1] = n
		data.append(n - 2)
	print(' '.join([str(a) for a in data]))
t = int(next(sys.stdin))
for i in range(t):
	n = int(next(sys.stdin))
	solve(n)


def solve_for_perm(perm):
	if perm == 1:
		print('1')
	if perm != 1:
		min_weight_perm = f'{perm}'
		list_rest_of_perm = map(str, range(1, perm))
		rest_of_perm = ' '.join(list_rest_of_perm)
		min_weight_perm = min_weight_perm + ' ' + rest_of_perm
		print(min_weight_perm)
inp_lines = int(input())
for i in range(inp_lines):
	perm = int(input())
	solve_for_perm(perm)


trails = int(input())
answer_list = []
for x in range(trails):
	s = int(input())
	ans = ''
	for d in range(2, s + 1):
		ans += str(d)
		ans += ' '
	ans += '1'
	answer_list.append(ans)
for g in answer_list:
	print(g)


import sys
printf = sys.stdout.write

def intput():
	return int(sys.stdin.readline())

def get_int():
	return map(int, sys.stdin.readline().strip().split())

def get_lis():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_liss():
	return sys.stdin.readline().split()

def get_ints():
	return sys.stdin.readline().split()

def get_str():
	return sys.stdin.readline().strip()

def pop_zeros(items):
	while items[-1] == 0:
		items.pop()
from collections import defaultdict
import math
t = intput()
while t:
	n = intput()
	ans = []
	if n % 2 == 0:
		for i in range(n):
			if i % 2 == 0:
				ans.append(i + 2)
			else:
				ans.append(i)
	else:
		for i in range(n - 1):
			if i % 2 == 0:
				ans.append(i + 2)
			else:
				ans.append(n - i + 1)
		ans.append(1)
	printf(' '.join((str(x) for x in ans)))
	printf('\n')
	t -= 1


for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(1)
	elif n == 2:
		print(2, 1)
	else:
		s = '2'
		for i in range(n - 2):
			s += ' ' + str(i + 3)
		s += ' ' + '1'
		print(s)


def main():
	t = int(input())
	for i in range(t):
		n = int(input())
		if n == 1:
			print(1)
		else:
			ans = [str(i) for i in range(2, n + 1)]
			ans.append('1')
			print(' '.join(ans))
main()


t = int(input())
for t in range(t):
	m = int(input())
	r = list(range(2, m + 1))
	r += [1]
	print(' '.join(map(str, r)))


for _ in range(int(input())):
	n = int(input())
	res = [i for i in range(2, n + 1)] + [1]
	res = list(map(str, res))
	print(' '.join(res))


for i in range(int(input())):
	n = int(input())
	a = [n]
	b = list(range(1, n))
	a.extend(b)
	print(' '.join(list(map(str, a))))


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


case = int(input())
for i in range(case):
	x = int(input())
	if x == 1:
		print('1')
	else:
		list1 = []
		list1.append(str(x))
		for j in range(x - 1):
			list1.append(str(j + 1))
		print(' '.join(list1))


for i in range(int(input())):
	n = int(input())
	if n == 1:
		print(1)
	else:
		a = [str(n)]
		a.extend([str(i) for i in range(1, n)])
		print(' '.join(a))


t = int(input())
for testcase in range(t):
	n = int(input())
	if n == 1:
		print('1')
		continue
	if n == 2:
		print('2 1')
		continue
	ans = [1]
	for i in range(2, n):
		if i % 2 == 0:
			ans.append(i + 1)
		else:
			ans.append(i - 1)
	if n % 2 == 0:
		ans[n - 2] = n
		ans.append(n - 2)
	else:
		ans.append(n - 1)
	out = str(ans)[1:-1].replace(',', '')
	print(out)


t = int(input())
for test in range(t):
	n = int(input())
	if n == 1:
		print(1)
	else:
		print(' '.join([str(i) for i in range(2, n + 1)]) + ' 1')


def permutation_weight(n):
	permutation = []
	permutation.append(n)
	for i in range(1, n):
		permutation.append(i)
	print(' '.join([str(s) for s in permutation]))
t = int(input())
for i in range(t):
	n = int(input())
	permutation_weight(n)


def solve():
	n = int(input())
	if n == 1:
		print(1)
	elif n & 1:
		res = [2, n]
		for i in range(1, n):
			if i == 2:
				continue
			res.append(i)
		print(' '.join(map(str, res)))
	else:
		res = []
		for i in range(1, n, 2):
			res.append(i + 1)
			res.append(i)
		print(' '.join(map(str, res)))
for _ in range(int(input())):
	solve()


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


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


def main():
	n = int(input())
	for x in range(n):
		ln = int(input())
		perm = list(range(1, ln + 1))
		perm.insert(0, perm.pop(-1))
		print(' '.join(map(str, perm)))
main()


for n in [*open(0)][1:]:
	print(*range(2, int(n) + 1), 1)


t = int(input())
for _ in range(t):
	num = int(input())
	if num == 1:
		print(1)
	else:
		print(num, end=' ')
		print(' '.join([str(i) for i in range(1, num)]))


t = int(input())
for i in range(t):
	n = int(input())
	L = []
	L.insert(0, n)
	for i in range(1, n):
		L.insert(i, i)
	print(' '.join(map(str, L)))


for _ in range(int(input())):
	n = int(input())
	if n == 1:
		l = ['1']
	elif n == 2:
		l = ['2', '1']
	else:
		l = [str(i) for i in range(3, n + 1)]
		l.insert(0, '1')
		l.append('2')
	print(' '.join(l))


def solution(n):
	s = str(n) + ' '
	for i in range(1, n):
		s += str(i) + ' '
	return s.strip()
t = int(input())
while t:
	n = int(input())
	print(solution(n))
	t -= 1


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


def solve():
	n = int(input())
	a = []
	i = 0
	a = list(range(1, n + 1))
	while i + 1 < n:
		(a[i], a[i + 1]) = (a[i + 1], a[i])
		i += 2
	if n & 1:
		(a[0], a[n - 1]) = (a[n - 1], a[0])
	return ' '.join((str(i) for i in a))
for _ in range(int(input())):
	ans = solve()
	print(ans)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	answer = [n] + [x for x in range(1, n)]
	answer = [str(x) for x in answer]
	print(' '.join(answer))


x = int(input())
for jj in range(x):
	n = int(input())
	arr = [n] + list(range(1, n))
	p = [str(i) for i in arr]
	print(' '.join(p))


def w(s):
	return sum([1 if s[i] % (i + 1) == 0 else 0 for i in range(len(s))])
for _ in range(int(input())):
	n = int(input())
	s = list(range(1, n + 1))
	s = s[1:] + s[0:1]
	print(' '.join([str(j) for j in s]))


def solve(v):
	if v == 1:
		return ''.join(['1'])

	def round(x, v):
		return x - 1 if x - 1 > 0 else x + v - 1
	return ' '.join([str(round(x, v)) for x in range(1, v + 1)])

def main():
	n = int(input())
	for _ in range(n):
		a = int(input())
		print(solve(a))
		pass
	pass
main()


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


def perm(n):
	L = []
	for i in range(n):
		L.append(i + 1)
	if n == 1:
		return n
	elif n % 2 == 0:
		L1 = L
		i = 1
		while i < n:
			(L1[i - 1], L1[i]) = (L1[i], L1[i - 1])
			i += 2
		s1 = ''
		for j in range(n):
			s1 += str(L1[j])
			s1 += ' '
		return s1
	else:
		L2 = L
		i = 2
		while i < n:
			(L2[i - 1], L2[i]) = (L2[i], L2[i - 1])
			i += 2
		s2 = ''
		for j in range(n):
			s2 += str(L2[j])
			s2 += ' '
		return s2
n_in = int(input())
p_lengths = []
for i in range(n_in):
	length = int(input())
	p_lengths.append(length)
for j in range(len(p_lengths)):
	print(perm(p_lengths[j]))


def solve(n):
	return [n] + [i for i in range(1, n)]
t = int(input())
while t:
	n = int(input())
	print(' '.join((str(x) for x in solve(n))))
	t -= 1


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


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


ans = ''
for _ in range(int(input())):
	n = int(input())
	if n == 1:
		ans += '1\n'
		continue
	arr = [i for i in range(1, n + 1)]
	for i in range(n - 1):
		(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
	if n % 2 == 1:
		(arr[0], arr[n - 1]) = (arr[n - 1], arr[0])
	for i in arr:
		ans += str(i) + ' '
	ans += '\n'
print(ans)


def perm(n):
	s = str(n)
	for i in range(n - 1):
		s += ' ' + str(i + 1)
	print(s)
for _ in range(int(input())):
	perm(int(input()))


for _ in range(int(input())):
	num = int(input())
	lis = [str(num)] + [str(x) for x in list(range(1, num))]
	print(' '.join(lis))


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


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


def sol(n):
	ans = [i for i in range(1, n)]
	return ' '.join(map(str, [n] + ans))
x = int(input())
for _ in range(x):
	n = int(input())
	print(sol(n))


t = int(input())

def solve():
	n = int(input())
	ans = [i for i in range(1, n + 1)]
	if n % 2 != 0:
		for i in range(1, n - 1, 2):
			(ans[i], ans[i + 1]) = (ans[i + 1], ans[i])
	else:
		for i in range(1, n - 2, 2):
			(ans[i], ans[i + 1]) = (ans[i + 1], ans[i])
		(ans[0], ans[-1]) = (ans[-1], ans[0])
	print(' '.join([str(ele) for ele in ans]))
while t:
	solve()
	t -= 1


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


def solve(n: int):
	perm = []
	for i in range(1, n + 1):
		if i == n:
			perm.append(str(1))
		else:
			perm.append(str(i + 1))
	return perm
t = int(input())
for _ in range(t):
	n = int(input())
	print(' '.join(solve(n)))


num_inp = lambda : int(input())
arr_inp = lambda : list(map(int, input().split()))
sp_inp = lambda : map(int, input().split())
str_inp = lambda : input()
t = num_inp()
for _ in range(t):
	n = num_inp()
	if n == 1:
		print(1)
	else:
		arr = []
		val = 2
		for i in range(n // 2):
			arr.extend([val, val - 1])
			val += 2
		if len(arr) != n:
			arr.append(val - 1)
			(arr[0], arr[-1]) = (arr[-1], arr[0])
		print(' '.join(map(str, arr)))


n = int(input())
for i in range(n):
	s = ''
	x = int(input())
	if x % 2 != 0:
		s += str(x)
		c = -1
		for j in range(1, x):
			r = j + 1 + c
			s += ' ' + str(r)
		print(s)
	else:
		c = 1
		for j in range(1, x + 1):
			r = j + c
			s += str(r) + ' '
			c *= -1
		print(s)


t = int(input())

def solve(n):
	if n == 1:
		return 1
	return ' '.join((str(i) for i in range(2, n + 1))) + ' 1'
while t:
	n = int(input())
	print(solve(n))
	t -= 1


n = int(input())

def perfect_per(number):
	if number == 1:
		return print(1)
	else:
		answer = [2]
		for j in range(number - 2):
			answer.append(j + 3)
	answer.append(1)
	print(' '.join(map(str, answer)))
	return answer
for i in range(n):
	number = int(input())
	perfect_per(number)


def mina(n):
	arr = n * ['0']
	if n % 2 == 0:
		m = 2
		for i in range(0, n, 2):
			arr[i] = str(m)
			arr[i + 1] = str(m - 1)
			m += 2
	else:
		m = 2
		for i in range(0, n - 1, 2):
			arr[i] = str(m)
			arr[i + 1] = str(m + 1)
			m += 2
		arr[n - 1] = '1'
	st = ' '.join(arr)
	return st
t = int(input())
for _ in range(0, t):
	n = int(input())
	response = mina(n)
	print(f'{response}')


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


import sys
Input = sys.stdin.readlines()
Output = []
t = int(Input[0])
for test in range(t):
	n = int(Input[test + 1])
	ans = []
	if n == 1:
		ans = [1]
	else:
		ans = [i + 2 for i in range(n - 1)] + [1]
	Output.append(ans)
for out in Output:
	print(*out)


n = input()
for i in range(int(n)):
	num = int(input())
	result = [i + 2 for i in range(num)]
	result[num - 1] = 1
	print(' '.join([str(v) for v in result]))


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


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


t = int(input())
for _ in range(t):
	n = int(input())
	print(f"{n} {' '.join((str(i) for i in range(1, n)))}")


t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	re = list()
	if n == 1:
		print(1)
		continue
	else:
		re.append(n)
		for i in range(1, n):
			re.append(i)
	print(str(re).replace('[', '').replace(']', '').replace(',', ''))


def get(n):
	l = []
	for x in range(n):
		p = str(x + 1)
		l.append(p)
	if n == 1:
		None
	elif n % 2 == 0:
		i = 0
		while i < n:
			(l[i], l[i + 1]) = (l[i + 1], l[i])
			i = i + 2
	else:
		i = 0
		while i < n - 1:
			(l[i], l[i + 1]) = (l[i + 1], l[i])
			i = i + 2
		(l[0], l[n - 1]) = (l[n - 1], l[0])
	print(listToString(l))

def listToString(s):
	str1 = ''
	for ele in s:
		str1 += ele + ' '
	return str1
t = int(input())
for x in range(t):
	n = int(input())
	get(n)


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


def main():
	n_tests = int(input())
	for _ in range(n_tests):
		n = int(input())
		if n == 1:
			print(n)
			continue
		result = []
		for a in range(2, n, 2):
			b = a + 1
			if b < n:
				result.append(b)
			result.append(a)
		result.append(1)
		if n % 2 > 0:
			(result[-1], result[-2]) = (result[-2], result[-1])
		result.insert(0, n)
		print(' '.join(map(str, result)))
main()


a = int(input(''))
var = []
for i in range(a):
	b = int(input(''))
	if b == 1:
		print(1)
	else:
		for i in range(1, b + 1):
			var.append(str(i))
		print(' '.join(var[1:] + var[:1]))
		var = []