I wonder, does the falling rain

Forever yearn for it's disdain?

Effluvium of the Mind

You are given a positive integer $n$.

Find any permutation $p$ of length $n$ such that the sum $\operatorname{lcm}(1,p_1) + \operatorname{lcm}(2, p_2) + \ldots + \operatorname{lcm}(n, p_n)$ is as large as possible.

Here $\operatorname{lcm}(x, y)$ denotes the least common multiple (LCM) of integers $x$ and $y$.

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 \le t \le 1000$). Description of the test cases follows.

The only line for each test case contains a single integer $n$ ($1 \le n \le 10^5$).

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


-----Output-----

For each test case print $n$ integers $p_1$, $p_2$, $\ldots$, $p_n$ — the permutation with the maximum possible value of $\operatorname{lcm}(1,p_1) + \operatorname{lcm}(2, p_2) + \ldots + \operatorname{lcm}(n, p_n)$.

If there are multiple answers, print any of them.


-----Examples-----

Input
2
1
2
Output
1 
2 1


-----Note-----

For $n = 1$, there is only one permutation, so the answer is $[1]$.

For $n = 2$, there are two permutations:

$[1, 2]$ — the sum is $\operatorname{lcm}(1,1) + \operatorname{lcm}(2, 2) = 1 + 2 = 3$.

$[2, 1]$ — the sum is $\operatorname{lcm}(1,2) + \operatorname{lcm}(2, 1) = 2 + 2 = 4$.

Difficulty: EASY
Tags: Greedy algorithms

Number theory

Constructive algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
t = int(input())
for _ in range(t):
	n = int(input())
	if n % 2 == 1:
		print(f"1 {' '.join((f'{k + 1} {k}' for k in range(2, n + 1, 2)))}")
	else:
		print(f"{' '.join((f'{k + 1} {k}' for k in range(1, n + 1, 2)))}")


from itertools import permutations
import math

def lcm(a, b):
	return a * b / math.gcd(a, b)

def lcm_sum(p):
	return sum([lcm(i + 1, x) for (i, x) in enumerate(p)])

def lcm_tuple(p):
	return [lcm(i + 1, x) for (i, x) in enumerate(p)]

def main_0():
	best = None
	for p in permutations(range(1, int(input()) + 1)):
		p_sum = lcm_sum(p)
		if best == None or p_sum > best[1]:
			best = (p, p_sum)
	print(' '.join(map(str, best[0])))

def main():
	p = list(range(1, int(input()) + 1))
	for i in range(len(p) - 2, -1, -2):
		cur = p[i]
		p[i] = p[i + 1]
		p[i + 1] = cur
	print(' '.join(map(str, p)))
for _ in range(int(input())):
	main()


from itertools import permutations
import math

def lcm(o, u):
	return o * u / math.gcd(o, u)

def lcm_sum(z):
	return sum([lcm(i + 1, x) for (i, x) in enumerate(z)])

def lcm_tuple(z):
	return [lcm(i + 1, x) for (i, x) in enumerate(z)]

def main_0():
	best = None
	for z in permutations(range(1, int(input()) + 1)):
		z_sum = lcm_sum(p)
		if best == None or z_sum > best[1]:
			best = (z, z_sum)
	print(' '.join(map(str, best[0])))

def main():
	z = list(range(1, int(input()) + 1))
	for i in range(len(z) - 2, -1, -2):
		cur = z[i]
		z[i] = z[i + 1]
		z[i + 1] = cur
	print(' '.join(map(str, z)))
for _ in range(int(input())):
	main()


tc = int(input())
while tc > 0:
	n = int(input())
	ans = []
	if n % 2 == 0:
		for i in range(1, n + 1, 2):
			ans.append(i + 1)
			ans.append(i)
	else:
		ans.append(1)
		for i in range(2, n + 1, 2):
			ans.append(i + 1)
			ans.append(i)
	print(' '.join(map(str, ans)))
	tc -= 1


def codeforces(n):
	res = [0 for i in range(n)]
	ind = n
	while ind > 1:
		res[ind - 1] = ind - 1
		res[ind - 2] = ind
		ind -= 2
	if ind == 1:
		res[0] = 1
	s = ' '.join(map(str, res))
	print(s)
t = int(input())
for test in range(t):
	n = int(input())
	codeforces(n)


t = int(input())

def generate_perm(n):
	if n % 2 == 1:
		perm = [1]
		for index in range(1, n - 1, 2):
			perm.extend([index + 2, index + 1])
		return perm
	else:
		perm = [2]
		for index in range(1, n - 1, 2):
			perm.extend([index, index + 3])
		perm.append(n - 1)
		return perm
for _ in range(t):
	n = int(input())
	print(' '.join((str(c) for c in generate_perm(n))))


for _ in range(int(input())):
	n = int(input())
	array = [] if n % 2 == 0 else [1]
	if n % 2 == 0:
		for num in range(1, n + 1, 2):
			array.extend([num + 1, num])
	else:
		for num in range(2, n + 1, 2):
			array.extend([num + 1, num])
	print(' '.join(map(str, array)))


import sys
input = sys.stdin.readline

def int_num():
	return int(input())

def int_list():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def solve():
	n = int_num()
	ans = []
	if n % 2 == 0:
		for i in range(1, n + 1, 2):
			ans.append(i + 1)
			ans.append(i)
	else:
		ans.append(1)
		for i in range(2, n + 1, 2):
			ans.append(i + 1)
			ans.append(i)
	print(' '.join(map(str, ans)))

def main():
	t = int_num()
	while t:
		solve()
		t -= 1
	return
main()


def solve():
	n = int(input())
	result = []
	if n % 2 == 0:
		for i in range(1, n + 1, 2):
			result.append(i + 1)
			result.append(i)
		return result
	else:
		for i in range(2, n + 1, 2):
			result.append(i + 1)
			result.append(i)
		return [1] + result
testNum = int(input())
for i in range(testNum):
	result = solve()
	print(' '.join([str(i) for i in result]))


def solution(n):
	ans = [str(i) for i in range(1, n + 1)]
	start = 0
	if n % 2 == 1:
		start = 1
	for i in range(start, len(ans), 2):
		(ans[i], ans[i + 1]) = (ans[i + 1], ans[i])
	print(' '.join(ans))
t = int(input())
for i in range(t):
	n = int(input())
	solution(n)


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


for _ in range(int(input())):
	n = int(input())
	if n % 2:
		ans = [1]
		s = 2
	else:
		ans = []
		s = 1
	for i in range(s, n + 1, 2):
		ans.extend([i + 1, i])
	print(' '.join(map(str, ans)))


import sys
for _ in range(int(input())):
	n = int(input())
	if n % 2 == 0:
		res = [0] * n
		x = 2
		for i in range(0, n, 2):
			res[i] = x
			res[i + 1] = x - 1
			x += 2
	else:
		res = [0] * n
		res[0] = 1
		x = 3
		for i in range(1, n, 2):
			res[i] = x
			res[i + 1] = x - 1
			x += 2
	sys.stdout.write(' '.join(map(str, res)) + '\n')


import sys

def solve():
	inp = sys.stdin.readline
	n = int(inp())
	a = list(range(1, n + 1))
	for i in range(n - 2, -1, -2):
		(a[i], a[i + 1]) = (a[i + 1], a[i])
	print(' '.join(map(str, a)))

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


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


import collections
import math

def solve():
	n = int(input())
	ls = []
	if n % 2 == 0:
		for i in range(n // 2):
			ls += [2 * (i + 1), 2 * i + 1]
	else:
		ls.append(1)
		for i in range((n - 1) // 2):
			ls += [2 * i + 3, 2 * i + 2]
	print(' '.join(map(str, ls)))
t = int(input())
for _ in range(t):
	solve()


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


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


T = int(input())
for t in range(T):
	n = int(input())
	b = list(range(1, n + 1))
	i = n - 1
	while i >= 1:
		(b[i], b[i - 1]) = (b[i - 1], b[i])
		i -= 2
	print(' '.join(map(str, b)))


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


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


for _ in range(int(input())):
	n = int(input())
	a = [i for i in range(1, n + 1)]
	if n % 2 == 0:
		i = 0
		while i < n - 1:
			(a[i], a[i + 1]) = (a[i + 1], a[i])
			i += 2
		print(' '.join(map(str, a)))
	else:
		a = a[1:n]
		i = 0
		while i < n - 1:
			(a[i], a[i + 1]) = (a[i + 1], a[i])
			i += 2
		print(1, ' '.join(map(str, a)))


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


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


t = int(input())
for i in range(t):
	a = int(input())
	if a % 2 == 1:
		s = '1 '
		for i in range(1, a // 2 + 1):
			s += str(2 * i + 1) + ' ' + str(2 * i) + ' '
	else:
		s = ''
		for i in range(1, a // 2 + 1):
			s += str(2 * i) + ' ' + str(2 * i - 1) + ' '
	print(s)


def solution(n):
	arr = list(range(1, n + 1))
	for i in range(n, 0, -2):
		if i - 2 >= 0:
			(arr[i - 1], arr[i - 2]) = (arr[i - 2], arr[i - 1])
	return ' '.join(map(str, arr))
N = int(input())
for _ in range(N):
	print(solution(int(input())))


t = int(input())
ans = []
for e in range(t):
	n = int(input())
	o = list(range(1, n + 1))
	for e in range(n % 2, n, 2):
		(o[e], o[e + 1]) = (o[e + 1], o[e])
	ans.append(' '.join(map(str, o)))
print('\n'.join(ans))


import sys
input = sys.stdin.readline
T = int(input())
while T:
	n = int(input())
	ans = []
	if n % 2 == 0:
		for i in range(n // 2):
			ans.append(2 * i + 2)
			ans.append(2 * i + 1)
	else:
		ans.append(1)
		for i in range(n // 2):
			ans.append(2 * i + 3)
			ans.append(2 * i + 2)
	print(' '.join(map(str, ans)))
	T -= 1


def fun(val):
	arr = []
	for i in range(val):
		arr.append(str(i + 1))
	if val % 2 == 0:
		for i in range(0, val, 2):
			(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
	else:
		for i in range(1, val, 2):
			(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
	return arr
n = int(input())
arr = []
for i in range(n):
	arr.append(int(input()))
for val in arr:
	if val == 1:
		print('1')
	else:
		print(' '.join(fun(val)))


n = int(input())
for i in range(n):
	m = int(input())
	rli = ''
	if m % 2 == 0:
		for k in range(m // 2):
			rli = rli + ' {0} {1}'.format(2 * k + 2, 2 * k + 1)
		rli = rli[1:]
	else:
		for k in range(m // 2):
			rli = rli + ' {0} {1}'.format(2 * k + 3, 2 * k + 2)
		rli = '1' + rli
	print(rli)


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


for _ in range(int(input())):
	n = int(input())
	l = list(range(1, n + 1))
	if n % 2 == 0:
		for i in range(0, len(l), 2):
			temp = l[i]
			l[i] = l[i + 1]
			l[i + 1] = temp
	else:
		for i in range(1, len(l), 2):
			temp = l[i]
			l[i] = l[i + 1]
			l[i + 1] = temp
	print(' '.join(map(str, l)))


for _ in range(int(input())):
	n = int(input())
	temp = [x for x in range(1, n + 1)]
	if n % 2 == 0:
		for j in range(0, n - 1, 2):
			(temp[j], temp[j + 1]) = (temp[j + 1], temp[j])
	else:
		for j in range(n - 1, 1, -2):
			(temp[j], temp[j - 1]) = (temp[j - 1], temp[j])
	temp = ' '.join(list(map(str, temp)))
	print(temp)


t = int(input())
for _ in range(t):
	n = int(input())
	res = [x for x in range(n)]
	for i in range(n - 1, -1, -2):
		if i > 0:
			res[i] = i - 1
			res[i - 1] = i
	print(' '.join((str(x + 1) for x in res)))


t = int(input())
for i in range(t):
	array = []
	n = int(input())
	if n % 2 == 0:
		for i in range(1, n + 1, 2):
			array.append(i + 1)
			array.append(i)
		print(' '.join((str(x) for x in array)))
	if n % 2 == 1:
		array.append(1)
		for i in range(2, n + 1, 2):
			array.append(i + 1)
			array.append(i)
		print(' '.join((str(x) for x in array)))


from re import A
for _ in range(int(input())):
	n = int(input())
	p = [0 for _ in range(n)]
	if n % 2 == 1:
		p[0] = 1
		for i in range(1, n, 2):
			p[i] = i + 2
			p[i + 1] = i + 1
	else:
		for i in range(0, n, 2):
			p[i] = i + 2
			p[i + 1] = i + 1
	print(' '.join(list(map(str, p))))


t = int(input())
end_mprint = []
for i in range(0, t):
	n = int(input())
	end_print = []
	if n % 2 == 1:
		a = 1
		end_print.append(1)
		for i in range(1, (n + 1) // 2):
			end_print.append(a + 2)
			a += 1
			end_print.append(a)
			a += 1
	else:
		a = 0
		for i in range(0, n // 2):
			end_print.append(a + 2)
			a += 1
			end_print.append(a)
			a += 1
	end_text_1 = str(end_print)
	end_text_2 = end_text_1.replace('[', '')
	end_text_3 = end_text_2.replace(']', '')
	end_text_4 = end_text_3.replace(',', '')
	end_mprint.append(end_text_4)
for i in range(0, t):
	print(end_mprint[i])


t = int(input())
result = []
for i in range(t):
	n = int(input())
	if n % 2 == 0:
		ch = ''
		init = 1
	else:
		ch = '1 '
		init = 2
	for j in range(init, n + 1, 2):
		ch += str(j + 1) + ' ' + str(j) + ' '
	result.append(ch)
for i in result:
	print(i)


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


def if_even(i, s):
	if i % 2 == 0 or i == 0:
		s.append(i + 2)
	elif i % 2 == 1:
		s.append(i)

def if_odd(i, s):
	if i == 0:
		s.append(1)
	elif i % 2 == 0:
		s.append(i)
	elif i % 2 == 1:
		s.append(i + 2)
cases = int(input())
for _ in range(cases):
	s = []
	n = int(input())
	for i in range(0, n):
		if n % 2 == 0:
			if_even(i, s)
		elif n % 2 == 1:
			if_odd(i, s)
	print(' '.join(map(str, s)))


trials = int(input())
answer_list = []
for x in range(trials):
	s = int(input())
	ans = '2'
	even = s % 2
	u = 0
	if even == 1:
		ans = '1'
		u = 1
	for d in range(2, s + 1):
		if even == 0:
			if d % 2 == 1:
				ans += ' ' + str(d + 1)
			else:
				ans += ' ' + str(d - 1)
		elif d % 2 == 0:
			ans += ' ' + str(d + 1)
		else:
			ans += ' ' + str(d - 1)
	answer_list.append(ans)
for g in answer_list:
	print(g)


def ans(n):
	p = []
	if n % 2 == 0:
		i = 1
		j = 2
		k = 1
		while k <= n:
			if k % 2 != 0:
				p.append(j)
				j = j + 2
			else:
				p.append(i)
				i = i + 2
			k += 1
		return p
	else:
		p.append(1)
		i = 3
		j = 2
		k = 2
		while k <= n:
			if k % 2 == 0:
				p.append(i)
				i = i + 2
			else:
				p.append(j)
				j = j + 2
			k += 1
		return p
t = int(input())
r = []
for i in range(t):
	n = int(input())
	r.append(ans(n))
for i in range(t):
	print(' '.join(map(str, r[i])))


q = int(input())
for w in range(q):
	n = int(input())
	A = [0] * n
	if n % 2 == 0:
		for i in range(n):
			if i % 2 == 0:
				A[i] = i + 2
			else:
				A[i] = i
	else:
		A = [0] * n
		A[0] = 1
		for i in range(1, n):
			if i % 2 == 1:
				A[i] = i + 2
			else:
				A[i] = i
	for i in range(n):
		A[i] = str(A[i])
	s = ' '.join(A)
	print(s)


for _ in range(int(input())):
	nu = int(input())
	num = list(range(1, nu + 1))
	if nu % 2 == 0:
		thing = list(reversed(range(0, nu, 2)))
	else:
		thing = list(reversed(range(1, nu - 1, 2)))
	for i in thing:
		(num[i], num[i + 1]) = (num[i + 1], num[i])
	print(' '.join([str(x) for x in num]))


t = int(input())
for i in range(t):
	n = int(input())
	L = []
	for i in range(1, n + 1):
		L.append(i)
	if n % 2 == 0:
		i = 0
		while i < n:
			(L[i], L[i + 1]) = (L[i + 1], L[i])
			i += 2
	else:
		i = 1
		while i < n:
			(L[i], L[i + 1]) = (L[i + 1], L[i])
			i += 2
	print(' '.join(map(str, L)))


p = int(input())
lst = []
for j in range(p):
	n = int(input())
	for i in range(n):
		if n % 2 == 0:
			if i == 0:
				lst.append(2)
			elif i % 2 == 0:
				lst.append(i + 2)
			else:
				lst.append(i)
		elif i == 0:
			lst.append(1)
		elif i % 2 == 0:
			lst.append(i)
		else:
			lst.append(i + 2)
	print(' '.join((str(x) for x in lst)))
	lst = []


k = int(input())
for x in range(k):
	firstline = int(input())
	if firstline == 1:
		print(1)
		continue
	if firstline == 2:
		print('2 1')
		continue
	if firstline % 2 == 1:
		intermediate = (firstline + 1) // 2
		oddlist = [x * 2 + 1 for x in range(1, intermediate)]
		evenlist = [x * 2 for x in range(1, intermediate)]
		outcome = list((list(y) for y in zip(oddlist, evenlist)))
		flat = '1 ' + ' '.join([str(item) for x in outcome for item in x])
		print(flat)
	else:
		intermediate = firstline // 2
		oddlist = [x * 2 - 1 for x in range(1, intermediate + 1)]
		evenlist = [x * 2 for x in range(1, intermediate + 1)]
		outcome = list((list(y) for y in zip(evenlist, oddlist)))
		flat = ' '.join([str(item) for x in outcome for item in x])
		print(flat)


t = int(input())
for testcases in range(t):
	n = int(input())
	res = ''
	i = 1
	if n % 2 == 0:
		while i <= n:
			if i % 2 == 0:
				res += f'{i - 1} '
			else:
				res += f'{i + 1} '
			i += 1
	else:
		while i <= n:
			if i == 1:
				res = res + '1 '
			elif i % 2 == 0:
				res += f'{i + 1} '
			else:
				res += f'{i - 1} '
			i += 1
	print(res)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(range(1, n + 1))
	delta = n % 2
	for i in range(n // 2):
		low = delta + i * 2
		high = low + 1
		(arr[low], arr[high]) = (arr[high], arr[low])
	print(' '.join([str(i) for i in arr]))


def solve():
	n = int(input())
	for _ in range(n):
		v = int(input())
		rarr = [i + 1 for i in range(v)]
		si = 1
		if v % 2:
			si = 2
		for i in range(si, v, 2):
			rarr[i] -= 1
			rarr[i - 1] += 1
		printVal(rarr)

def printVal(arr):
	s = ''
	for val in arr:
		s += str(val)
		s += ' '
	s = s[0:len(s) - 1]
	print(s)
solve()


case = int(input())
for i in range(case):
	n = int(input())
	ans = []
	for j in range(n):
		ans.append(j + 1)
	x = n // 2
	if n == 1:
		print('1')
	elif n == 2:
		print('2 1')
	elif n % 2 == 0:
		for k in range(x):
			(ans[2 * k], ans[2 * k + 1]) = (str(ans[2 * k + 1]), str(ans[2 * k]))
		print(' '.join(ans))
	else:
		for k in range(x):
			ans[0] = str(ans[0])
			(ans[2 * k + 1], ans[2 * k + 2]) = (str(ans[2 * k + 2]), str(ans[2 * k + 1]))
		print(' '.join(ans))


import sys
import heapq
from math import log10, floor, pow
from collections import defaultdict, deque
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
tests = inp()
for test in range(tests):
	n = inp()
	lt = [x for x in range(1, n + 1)]
	for i in range(len(lt) - 1, 0, -2):
		(lt[i], lt[i - 1]) = (lt[i - 1], lt[i])
	ans = ''
	for i in lt:
		ans += str(i) + ' '
	print(ans[:-1])


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(range(1, n + 1))
	start = n % 2
	point = start
	while point < n:
		arr[point] = arr[point] + arr[point + 1]
		arr[point + 1] = arr[point] - arr[point + 1]
		arr[point] = arr[point] - arr[point + 1]
		point += 2
	print(' '.join((str(i) for i in arr)))


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


for _ in range(int(input())):
	a = int(input())
	t = []
	if a % 2 == 0:
		for i in range(1, a + 1, 2):
			t.append(i + 1)
			t.append(i)
	elif a % 2 == 1:
		t = [1]
		for zzz in range(2, a + 1, 2):
			t.append(zzz + 1)
			t.append(zzz)
	ans = ''
	for z in t:
		ans += str(z) + ' '
	print(ans)


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 % 2 == 0:
		for i in range(1, n + 1, 2):
			print(f'{i + 1} {i}', end=' ')
	else:
		print(1, end=' ')
		for i in range(2, n + 1, 2):
			print(f'{i + 1} {i}', end=' ')
	print()


import sys
sys.setrecursionlimit(1000000000)
from collections import defaultdict, deque
from functools import lru_cache
from bisect import bisect_left, bisect_right, insort_right, insort_left
import heapq
from itertools import accumulate
for _ in range(int(input())):
	n = int(input())
	nums = list(range(1, n + 1))
	for i in range(n - 1, 0, -2):
		(nums[i], nums[i - 1]) = (nums[i - 1], nums[i])
	print(' '.join((str(i) for i in nums)))


t = int(input())
for i in range(t):
	n = int(input())
	h = list(range(1, n + 1))
	if n % 2 == 0:
		for j in range(0, n, 2):
			p = h[j]
			h[j] = h[j + 1]
			h[j + 1] = p
		re = ''
		for j in range(n):
			re += str(h[j]) + ' '
		print(re)
	else:
		for j in range(1, n, 2):
			p = h[j]
			h[j] = h[j + 1]
			h[j + 1] = p
		re = ''
		for j in range(n):
			re += str(h[j]) + ' '
		print(re)


for _ in range(int(input())):
	n = int(input())
	A = []
	B = []
	s = ''
	for i in range(1, n + 1):
		A.append(i)
	for j in range(len(A) - 1, 0, -2):
		B.append(A[j - 1])
		B.append(A[j])
	if 1 not in B:
		B.append(1)
	B = B[::-1]
	for ele in B:
		s += str(ele) + ' '
	print(s)


class Solution:

	def permute(self, n):
		isOdd = n % 2 == 1
		if n == 1:
			return '1'
		odd = [n for n in range(3, n + 1) if n % 2 == 1]
		even = [n for n in range(2, n + 1) if n % 2 == 0]
		if isOdd:
			even = [1] + even
		else:
			odd = [1] + odd
		res = []
		for i in range(max(len(odd), len(even))):
			if i < len(even):
				res.append(str(even[i]))
			if i < len(odd):
				res.append(str(odd[i]))
		return ' '.join(list(map(str, res)))
t = int(input())
rs = []
for _ in range(t):
	n = int(input())
	rs.append(n)
sol = Solution()
for n in rs:
	print(sol.permute(n))


import sys
input = sys.stdin.readline
M = int(1000000000.0) + 7

def solve():
	n = int(input())
	ans = []
	i = 1
	if n % 2 == 1:
		ans.append(1)
		i = 2
	while i < n:
		ans.append(i + 1)
		ans.append(i)
		i += 2
	return ans
for _ in range(int(input())):
	print(*solve())


t = int(input())
while t:
	t -= 1
	n = int(input())
	s = [i for i in range(1, n + 1)]
	i = len(s) - 1
	while i >= 1:
		(s[i], s[i - 1]) = (s[i - 1], s[i])
		i -= 2
	ans = ''
	for i in s:
		ans += str(i)
		ans += ' '
	print(ans[:-1])


tests = int(input())
while tests > 0:
	tests -= 1
	n = int(input())
	p = []
	out = ''
	a = True
	aa = []
	b = True
	out1 = '1 '
	odd = 3
	evenn = 2
	oddn = 3
	odd = True
	z = 1
	if n % 2 == 1:
		while z < n:
			if odd:
				out1 += str(oddn) + ' '
				oddn += 2
				odd = False
			else:
				out1 += str(evenn) + ' '
				evenn += 2
				odd = True
			z += 1
	else:
		out1 = '2 1 '
		oddn = 3
		evenn = 4
		odd = False
		while z < n - 1:
			if odd:
				out1 += str(oddn) + ' '
				oddn += 2
				odd = False
			else:
				out1 += str(evenn) + ' '
				evenn += 2
				odd = True
			z += 1
	print(out1)


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	ans = []
	for i in range(n, 1, -2):
		ans.append(i - 1)
		ans.append(i)
	if n % 2:
		ans.append(1)
	return ans[::-1]
for _ in range(int(input())):
	print(*solve())


for num in [*map(int, open(0))][1:]:
	a1 = [1] * num
	for i in range(num, 1, -2):
		a1[i - 2:i] = (i, i - 1)
	print(*a1)


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


T = int(input())
q = []
for i in range(T):
	nb = int(input())
	q.append(nb)

def solve(nb):
	start = 1
	if nb & 1:
		print(1, end=' ')
		start += 1
	for i in range(start, nb + 1, 2):
		print(i + 1, i, sep=' ', end=' ')
	print()
for nb in q:
	solve(nb)


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


for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(1)
		continue
	if n == 2:
		print('2 1')
		continue
	a = [i + 1 for i in range(n)]
	b = []
	if n % 2 == 0:
		for i in range(1, n, 2):
			b.append(i + 1)
			b.append(i)
		print(*b, sep=' ')
		continue
	b = [1]
	for i in range(2, n, 2):
		b.append(i + 1)
		b.append(i)
	print(*b, sep=' ')


t = int(input())
for i in range(0, t):
	n = int(input())
	b = list()
	if n % 2 == 0:
		for i in range(1, n + 1, 2):
			b.append(i + 1)
			b.append(i)
	else:
		b.append(1)
		for i in range(2, n + 1, 2):
			b.append(i + 1)
			b.append(i)
	print(*b, sep=' ')


for _ in range(int(input())):
	n = int(input())
	arr = list(range(0, n + 1))
	if n % 2:
		for x in range(1, n + 1, 2):
			arr[x] = max(x - 1, 1)
		for x in range(2, n + 1, 2):
			arr[x] = x + 1
	else:
		for x in range(1, n + 1, 2):
			arr[x] = x + 1
		for x in range(2, n + 1, 2):
			arr[x] = x - 1
	print(*arr[1:], sep=' ')


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


def solve():
	n = int(input())
	k = 1
	ans = []
	if n % 2 == 1:
		ans.append(k)
		k += 1
	for i in range(n // 2):
		ans.append(k + 1)
		ans.append(k)
		k += 2
	print(*ans)
for i in range(int(input())):
	solve()


testcase = int(input())
for i in range(testcase):
	n = int(input())
	sum = 0
	if n % 2 == 0:
		for i in range(0, n, 2):
			print(i + 2, i + 1, sep=' ', end=' ')
	else:
		print(1, end=' ')
		for i in range(0, n - 1, 2):
			print(i + 3, i + 2, sep=' ', end=' ')
	print()


def solve():
	n = int(input())
	ls = []
	for i in range(1, n + 1):
		ls.append(i)
	for i in range(n % 2, n, 2):
		(ls[i], ls[i + 1]) = (ls[i + 1], ls[i])
	print(*ls)
for i in range(int(input())):
	solve()


for _ in range(int(input())):
	x = int(input())
	if not x % 2:
		print(*[n + 1 if n % 2 else n - 1 for n in range(1, x + 1)])
	else:
		print(*[1] + [n - 1 if n % 2 else n + 1 for n in range(2, x + 1)])


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


def main():
	for t in range(int(input())):
		n = int(input())
		ans = []
		if n % 2 == 0:
			for i in range(2, n + 1, 2):
				ans.append(i)
				ans.append(i - 1)
		else:
			ans.append(1)
			for i in range(3, n + 1, 2):
				ans.append(i)
				ans.append(i - 1)
		print(*ans)
main()


def solution(n):
	arr = []
	if n % 2 == 0:
		for i in range(1, n + 1):
			if i % 2 == 0:
				arr.append(i - 1)
			else:
				arr.append(i + 1)
	else:
		arr.append(1)
		for i in range(2, n + 1):
			if i % 2 == 0:
				arr.append(i + 1)
			else:
				arr.append(i - 1)
	return arr
t = int(input())
while t:
	n = int(input())
	arr = solution(n)
	print(*arr)
	t -= 1


from collections import Counter, defaultdict
from heapq import heapify, heappop, heappush
reps = int(input())
for _ in range(reps):
	n = int(input())
	if n % 2:
		arr = [1]
		for (a, b) in zip(range(3, n + 1, 2), range(2, n, 2)):
			arr.append(a)
			arr.append(b)
	else:
		arr = []
		for (a, b) in zip(range(2, n + 1, 2), range(1, n, 2)):
			arr.append(a)
			arr.append(b)
	print(*arr)


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


for n in [*map(int, open(0))][1:]:
	a = [1] * n
	for i in range(n, 1, -2):
		a[i - 2:i] = (i, i - 1)
	print(*a)


for _ in range(int(input())):
	num = int(input())
	re = []
	if num % 2:
		re.append(1)
		for i in range(2, num + 1, 2):
			re.append(i + 1)
			re.append(i)
	else:
		for i in range(1, num + 1, 2):
			re.append(i + 1)
			re.append(i)
	print(*re)


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


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


for i in range(int(input())):
	n = int(input())
	k = []
	if n % 2 == 0:
		for i in range(2, n + 1, 2):
			k.append(i)
			k.append(i - 1)
	else:
		k = [1]
		if n == 1:
			pass
		for i in range(3, n + 1, 2):
			k.append(i)
			k.append(i - 1)
	print(*k)


def sol():
	n = int(input())
	ans = []
	if n % 2 == 0:
		for i in range(n, 0, -1):
			if i % 2 == 0:
				ans.append(i - 1)
			else:
				ans.append(i + 1)
	else:
		for i in range(n, 1, -1):
			if i == n:
				ans.append(i - 1)
			elif i % 2 == 0:
				ans.append(i + 1)
			else:
				ans.append(i - 1)
		ans.append(1)
	print(*ans[::-1], sep=' ')
for _ in range(int(input())):
	sol()


for t in range(int(input())):
	n = int(input())
	a = []
	if n & 1:
		a.append(1)
		for (x, y) in zip(range(2, n + 1, 2), range(3, n + 1, 2)):
			a.extend([y, x])
	else:
		for (x, y) in zip(range(1, n + 1, 2), range(2, n + 1, 2)):
			a.extend([y, x])
	print(*a)


import sys
t = int(sys.stdin.readline())
info = []
for i in range(t):
	info.append(int(sys.stdin.readline()))
res = []

def nod(x, y):
	a = min(x, y)
	for i in range(a + 1, 0, -1):
		if x % i == 0 and y % i == 0:
			return i
for i in range(t):
	arr = range(1, info[i] + 1)
	ans = [0] * info[i]
	if info[i] % 2 == 1:
		ans[0] = 1
		for i in range(1, info[i]):
			if i % 2 == 1:
				ans[i] = arr[i + 1]
			else:
				ans[i] = arr[i - 1]
	else:
		for i in range(1, info[i], 2):
			(ans[i], ans[i - 1]) = (arr[i - 1], arr[i])
	res.append(ans)
for i in res:
	for k in i:
		sys.stdout.write(str(k) + ' ')
	sys.stdout.write('\n')


t = int(input())

def swap(nums):
	for i in range(0, len(nums) - len(nums) % 2, 2):
		(nums[i], nums[i + 1]) = (nums[i + 1], nums[i])
	return nums
for _ in range(t):
	n = int(input())
	a = [i for i in range(1, n + 1)]
	if n % 2 == 0:
		print(*swap(a))
	else:
		a.sort(reverse=True)
		b = swap(a)
		print(*reversed(b))