A permutation of length n is an array of size n consisting of n distinct integers in the range [1, n]. For example, (3, 2, 4, 1) is a permutation of length 4, but (3, 3, 1, 4) and (2, 3, 4, 5) are not, as (3, 3, 1, 4) contains duplicate elements, and (2, 3, 4, 5) contains elements not in range [1,4].
A permutation p of length n is good if and only if for any 1 ≤ i ≤ n, pi ≠ i.
Please find the lexicographically smallest good permutation p.
Definition for "lexicographically smaller":
For two permutations p and q, we say that p is lexicographically smaller than q if and only if there exists a index 1 ≤ l ≤ n such that:
- For any 1 ≤ i < l, pi = qi. Note that if l = 1, this constraint means nothing.
- and, pl < ql.

For example, (2, 3, 1, 4) < (2, 3, 4, 1) < (3, 4, 1, 2). The lexicographically smallest permutation is, of course, (1, 2, ..., n), though this one is not good.

-----Input-----
First line of the input contains an integer T denoting number of test cases.
For each test case, the only line contains an integer n.

-----Output-----
For each test case, output the lexicographically smallest good permutation of length n. It's guaranteed that this permutation exists.

-----Constraints-----
- 1 ≤ T ≤ 10
- 2 ≤ n ≤ 105

-----Subtasks-----
- Subtask #1 (17 points): 2 ≤ n ≤ 9
- Subtask #2 (83 points): Original Constraints

-----Example-----
Input:
4
2
3
5
6

Output:
2 1
2 3 1
2 1 4 5 3
2 1 4 3 6 5

-----Explanation-----
Example case 1. The only good permutation of length 2 is (2, 1).
Example case 2. Consider all permutations of length 3, they are(in lexicographically order):
- p = (1, 2, 3), it's not good since p[1] = 1, p[2] = 2 and p[3] = 3;
- p = (1, 3, 2), it's not good since p[1] = 1;
- p = (2, 1, 3), it's not good since p[3] = 3;
- p = (2, 3, 1), it's good since p[1] ≠ 1, p[2] ≠ 2 and p[3] ≠ 3;
- p = (3, 1, 2), it's good since p[1] ≠ 1, p[2] ≠ 2 and p[3] ≠ 3;
- p = (3, 2, 1), it's not good since p[2] = 2.
Thus the minimum good one is (2, 3, 1).
Example case 3. Consider two good permutations for third test case: p=(2, 1, 4, 5, 3) and q=(2, 4, 1, 5, 3), then p < q. You can check lexicographically condition as follows. Find the first index where the entries of two permutations are different, and compare those entries. For example, in this case, the first position where the entries differ is index 2. You can see that p[2] < q[2], as 1 < 4, so p is lexicographically smaller than q.

Difficulty: EASY
Tags: Constructive algorithms

Ad-hoc

Starter code:

Solutions:
try:
	t = int(input(''))
	for i in range(t):
		n = int(input(''))
		count = 0
		x = 2
		y = 1
		if n % 2 == 0:
			while count < n:
				for w in range(2, n + 1):
					print(x, end=' ')
					count += 1
					x += 2
					break
				for e in range(1, n, 2):
					print(y, end=' ')
					count += 1
					y += 2
					break
			print('\n')
		if n % 2 != 0:
			while count < n - 3:
				for w in range(2, n - 2, 2):
					print(x, end=' ')
					count += 1
					x += 2
					break
				for e in range(1, n - 2, 2):
					print(y, end=' ')
					count += 1
					y += 2
					break
			print(n - 1, end=' ')
			print(n, end=' ')
			print(n - 2, end=' ')
			print('\n')
except:
	exit()


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


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


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


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


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


for _ in range(int(input())):
	n = int(input())
	if n == 2:
		print(*[2, 1])
	elif n == 3:
		print(*[2, 3, 1])
	else:
		arr = list(range(1, n + 1))
		for i in range(1, n, 2):
			if n % 2 == 1 and n - i == 2:
				(arr[i - 1], arr[i], arr[i + 1]) = (arr[i], arr[i + 1], arr[i - 1])
				break
			else:
				(arr[i], arr[i - 1]) = (arr[i - 1], arr[i])
		print(*arr)


try:
	t = int(input())
	for _ in range(t):
		n = int(input())
		odd = 0
		if n & 1:
			odd = 1
			n -= 3
		arr = []
		for i in range(1, n + 1, 2):
			arr.append(i + 1)
			arr.append(i)
		if odd:
			arr.append(n + 2)
			arr.append(n + 3)
			arr.append(n + 1)
		for i in arr:
			print(i, end=' ')
		print()
except:
	pass


for _ in range(int(input())):
	n = int(input())
	l = [i for i in range(1, n + 1)]
	for i in range(n):
		if l[i] == i + 1:
			try:
				(l[i], l[i + 1]) = (l[i + 1], l[i])
			except:
				(l[i], l[i - 1]) = (l[i - 1], l[i])
	for item in l:
		print(item, end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	l = []
	x = 1
	while x < n:
		l += [x + 1, x]
		x += 2
	if n % 2 == 1:
		l.append(l[-1])
		l[-2] = n
	print(*l)


try:
	for _ in range(int(input())):
		N = int(input())
		odd = False
		li = [0] * N
		if N & 1 == 1:
			odd = True
			N -= 3
		for i in range(0, N, 2):
			li[i] = i + 2
			li[i + 1] = i + 1
		if odd:
			li[N] = N + 2
			li[N + 1] = N + 3
			li[N + 2] = N + 1
		print(*li)
except Exception as e:
	print(e.__class__)


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


T = int(input())
for i in range(T):
	n = int(input())
	permutation = [j + 1 for j in range(n)]
	if n % 2:
		for i in range(n - 1):
			if i % 2:
				permutation[i] -= 1
			else:
				permutation[i] += 1
		flip = permutation[n - 2]
		permutation[n - 2] = permutation[n - 1]
		permutation[n - 1] = flip
	else:
		for i in range(n):
			if i % 2:
				permutation[i] -= 1
			else:
				permutation[i] += 1
	print(*permutation)


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


try:
	t = int(input())
	for _ in range(t):
		n = int(input())
		r = []
		if n % 2 == 0:
			for i in range(1, n + 1):
				if i % 2 != 0:
					r.append(i + 1)
				else:
					r.append(i - 1)
		elif n == 3:
			r.append(n - 1)
			r.append(n)
			r.append(n - 2)
		else:
			for i in range(1, n - 2):
				if i % 2 != 0:
					r.append(i + 1)
				else:
					r.append(i - 1)
			r.append(n - 1)
			r.append(n)
			r.append(n - 2)
		print(*r)
except:
	pass


T = int(input())
while T > 0:
	T -= 1
	k = int(input())
	perm = []
	if k % 2 == 0:
		for i in range(2, k + 1, 2):
			perm.append(i)
			perm.append(i - 1)
	else:
		r = k - 3
		for i in range(2, k - 2, 2):
			perm.append(i)
			perm.append(i - 1)
		perm.extend([k - 1, k, k - 2])
	for i in perm:
		print(i, end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	if n <= 3:
		l = [i for i in range(2, n + 1)]
		l = l + [1]
		print(*l)
	elif n == 4:
		print(2, 1, 4, 3)
	elif n == 5:
		print(2, 1, 4, 5, 3)
	else:
		l = [i for i in range(1, n + 1)]
		if n % 2 == 0:
			for i in range(0, n, 2):
				(l[i], l[i + 1]) = (l[i + 1], l[i])
			print(*l)
		else:
			for i in range(0, n - 4, 2):
				(l[i], l[i + 1]) = (l[i + 1], l[i])
			(l[-3], l[-2], l[-1]) = (l[-2], l[-1], l[-3])
			print(*l)


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


try:
	for _ in range(int(input())):
		n = int(input())
		l = []
		if n % 2 == 0:
			for i in range(1, n + 1):
				if i % 2 == 0:
					l.append(str(i - 1))
				else:
					l.append(str(i + 1))
		else:
			for j in range(1, n - 1):
				if j % 2 == 0:
					l.append(str(j - 1))
				else:
					l.append(str(j + 1))
			l.append(str(n))
			l.append(str(n - 2))
		print(' '.join(l))
except:
	pass


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


tests = int(input())
for t in range(tests):
	n = int(input())
	permut = '2'
	permut_list = []
	if n % 2 == 0:
		for i in range(2, n + 1):
			if i % 2 == 1:
				permut = permut + ' ' + str(i + 1)
			else:
				permut = permut + ' ' + str(i - 1)
		print(permut)
		pass
	elif n == 1:
		print(1)
		pass
	else:
		for i in range(2, n):
			if i % 2 == 1:
				permut_list.append(str(i + 1))
			else:
				permut_list.append(str(i - 1))
		permut_list.pop(-1)
		permut_list.append(str(n))
		permut_list.append(str(n - 2))
		this_permut = '2'
		for el in permut_list:
			this_permut = this_permut + ' ' + el
		print(this_permut)


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


import sys, math, numpy as np
from sys import stdin, stdout
mod = int(1000000000.0 + 7)
from statistics import mode
from collections import deque, defaultdict
from math import ceil, floor, inf, factorial, gcd, log2
ii1 = lambda : int(stdin.readline().strip())
is1 = lambda : stdin.readline().strip()
iia = lambda : list(map(int, stdin.readline().strip().split()))
isa = lambda : stdin.readline().strip().split()

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

def setbits(n):
	return bin(n).count('1')

def resetbits(n):
	return bin(n).count('0')

def modinv(n, p):
	return pow(n, p - 2, p)

def ncr_p(n, r, p):
	(num, den) = (1, 1)
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * modinv(den, p) % p

def isPrime(num):
	if num <= 1:
		return False
	if num == 2 or n == 3:
		return True
	if num % 2 == 0 or num % 3 == 0:
		return False
	for i in range(5, int(num ** 0.5) + 1, 6):
		if num % i == 0 or num % (i + 2) == 0:
			return False
	return True

def bin_search(arr, low, high, val):
	while low <= high:
		mid = low + (high - low) // 2
		if arr[mid] == val:
			return mid
		elif arr[mid] < val:
			low = mid + 1
		else:
			high = mid - 1
	return -1

def sumofdigit(num):
	count = 0
	while num:
		count += num % 10
		num //= 10
	return count

def make_dic(arr):
	freq = {}
	for val in arr:
		freq[val] = freq[val] + 1 if val in freq else 1
	return freq

def inputmatrix():
	(r, c) = iia()
	mat = [0] * r
	for i in range(r):
		mat[i] = iia()
	return mat

def prefix_sum(n, arr):
	for i in range(1, n):
		arr[i] += arr[i - 1]
	return arr

def binomial(n, k):
	if 0 <= k <= n:
		ntok = 1
		ktok = 1
		for t in range(1, min(k, n - k) + 1):
			ntok *= n
			ktok *= t
			n -= 1
		return ntok // ktok
	else:
		return 0

def divisors(n):
	res = []
	for i in range(1, ceil(sqrt(n)) + 1):
		if n % i == 0:
			if i == n // i:
				res.append(i)
			else:
				res.append(i)
				res.append(n // i)
	return res
for _ in range(ii1()):
	n = ii1()
	dp = [0] * (n + 1)
	if n & 1:
		for i in range(1, n - 2):
			if i & 1:
				dp[i] = i + 1
			else:
				dp[i] = i - 1
		dp[n - 2] = n - 1
		dp[n - 1] = n
		dp[n] = n - 2
		for i in range(1, n + 1):
			print(dp[i], end=' ')
		print()
	else:
		for i in range(1, n + 1):
			if i & 1:
				dp[i] = i + 1
			else:
				dp[i] = i - 1
		for i in range(1, n + 1):
			print(dp[i], end=' ')
		print()


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


tests = int(input())
for i in range(tests):
	n = int(input())
	ans = []
	if n & 1:
		end = n - 2
	else:
		end = n + 1
	for j in range(1, end):
		if j & 1:
			ans.append(j + 1)
		else:
			ans.append(j - 1)
	for k in range(end, n + 1):
		if k == n:
			ans.append(k - 2)
		else:
			ans.append(k + 1)
	print(*ans)


tc = int(input())
for _ in range(tc):
	n = int(input())
	k = n // 2 - 1
	if n % 2 == 0:
		k = n // 2
	res = [0] * n
	for i in range(1, 2 * k + 1, 2):
		res[i - 1] = i + 1
	for i in range(2, 2 * k + 1, 2):
		res[i - 1] = i - 1
	if n % 2 == 1:
		res[n - 3] = n - 1
		res[n - 2] = n
		res[n - 1] = n - 2
	print(*res, sep=' ')


import sys
import math

def main(n):
	arr = []
	for i in range(1, n + 1):
		arr.append(i)
	i = 0
	j = 1
	while i < n and j < n:
		(arr[i], arr[j]) = (arr[j], arr[i])
		i += 2
		j += 2
	if n & 1:
		(arr[-2], arr[-1]) = (arr[-1], arr[-2])
	print(*arr)
	return
for _ in range(int(input())):
	n = int(input())
	main(n)


for _ in range(int(input())):
	n = int(input())
	if n % 2 == 0:
		ans = []
		c = 1
		while c <= n:
			ans.append(c + 1)
			ans.append(c)
			c += 2
		print(*ans)
	else:
		aux = [n - 1, n, n - 2]
		ans = []
		c = 1
		while c <= n - 3:
			ans.append(c + 1)
			ans.append(c)
			c += 2
		ans = ans + aux
		print(*ans)


try:
	t = int(input())
	for _ in range(t):
		n = int(input())
		a = []
		count = 1
		for i in range(n):
			if i % 2 == 0:
				if i == n - 1:
					if n % 2 == 1:
						a.append(i - 1)
						continue
				a.append(count * 2)
				count += 1
			elif n % 2 == 1:
				if i == n - 2:
					a.append(i + 2)
				elif i == n - 1:
					a.append(i - 1)
				else:
					a.append(i)
			else:
				a.append(i)
		print(*a)
except:
	pass


T = int(input())
ip = []
while T > 0:
	ip.append(int(input()))
	T -= 1
op = []
o = []
for i in ip:
	o = []
	if i % 2 == 0:
		for j in range(1, i + 1):
			if j % 2 == 0:
				o.append(j - 1)
			else:
				o.append(j + 1)
	elif i % 2 == 1:
		for j in range(1, i - 2):
			if j % 2 == 0:
				o.append(j - 1)
			else:
				o.append(j + 1)
		o.append(i - 1)
		o.append(i)
		o.append(i - 2)
	op.append(o)
for i in op:
	for j in i:
		print(j, end=' ')
	print('')


from sys import stdin
try:
	t = eval(stdin.readline())
	for _ in range(t):
		n = eval(stdin.readline())
		arr = [x for x in range(1, n + 1)]
		if n % 2 == 0:
			for i in range(0, n - 1, 2):
				(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
		else:
			for i in range(0, n, 2):
				if i < n - 2:
					(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
				else:
					(arr[i], arr[i - 1]) = (arr[i - 1], arr[i])
		print(' '.join(list(map(str, arr))))
except:
	pass


for i in range(int(input())):
	n = int(input())
	a = 2
	b = 1
	flag = False
	if n % 2 != 0:
		limit = n - 2
		flag = True
	else:
		limit = n
	for i in range(limit):
		if i % 2 == 0:
			t = a
			a = a + 2
		else:
			t = b
			b = b + 2
		print(t, end=' ')
	if flag:
		print(t + 1, t - 1, end=' ')
	print()


import numpy as np
try:
	t = int(input())
	for _ in range(t):
		n = int(input())
		nList = np.arange(start=1, stop=n + 1)
		if n % 2 != 0:
			i = 0
			while i < nList.__len__() - 1:
				t = nList[i]
				nList[i] = nList[i + 1]
				nList[i + 1] = t
				i = i + 2
			temp = nList[-1]
			nList[-1] = nList[-2]
			nList[-2] = temp
		elif n % 2 == 0:
			i = 0
			while i < nList.__len__() - 1:
				t = nList[i]
				nList[i] = nList[i + 1]
				nList[i + 1] = t
				i = i + 2
		print(*nList)
except:
	pass


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


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


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


n = int(input())
for _ in range(n):
	lst = []
	n = int(input())
	for i in range(1, n + 1):
		lst.append(i)
	if len(lst) % 2 == 0:
		for j in range(len(lst)):
			if j % 2 == 0:
				lst[j] = lst[j] + 1
			else:
				lst[j] = lst[j] - 1
	elif len(lst) % 2 == 1:
		for j in range(len(lst)):
			if j % 2 == 0:
				lst[j] = lst[j] + 1
			else:
				lst[j] = lst[j] - 1
		lst[-2] = lst[-2] + 2
		lst[-1] = lst[-1] - 3
	print(*lst)


for _ in range(int(input())):
	a = list(map(lambda x: str(x), range(1, int(input()) + 1)))
	b = []
	if len(a) % 2 == 0:
		for i in range(0, len(a), 2):
			b.append(a[i + 1])
			b.append(a[i])
		print(' '.join(b))
	else:
		for j in range(0, len(a) - 3, 2):
			b.append(a[j + 1])
			b.append(a[j])
		b.append(a[-2])
		b.append(a[-1])
		b.append(a[-3])
		print(' '.join(b))


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


for _ in range(int(input())):
	n = int(input())
	a = list(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(0, n - 1, 2):
			(a[i], a[i + 1]) = (a[i + 1], a[i])
		(a[-1], a[-2]) = (a[-2], a[-1])
	for x in a:
		print(x, end=' ')
	print()


t = input()
for c in range(0, int(t)):
	n = int(input())
	ans = []
	if n & 1:
		end = n - 2
	else:
		end = n + 1
	for j in range(1, end):
		if j & 1:
			ans.append(j + 1)
		else:
			ans.append(j - 1)
	for k in range(end, n + 1):
		if k == n:
			ans.append(k - 2)
		else:
			ans.append(k + 1)
	print(*ans)


t = int(input())
for i in range(t):
	n = int(input())
	if n == 3:
		print('2 3 1')
	else:
		l = [0] * n
		x = 2
		for j in range(0, n, 2):
			l[j] = x
			x += 2
		x = 1
		for k in range(1, n, 2):
			l[k] = x
			x += 2
		if n % 2 == 0:
			print(*l)
		else:
			l[-1] = n - 2
			l[-2] = n
			l[-3] = n - 1
			print(*l)


for test in range(int(input())):
	n = int(input())
	int_n = n if n % 2 == 0 else n - 1
	int_ans = list(range(1, int_n + 1))
	for i in range(1, len(int_ans), 2):
		(int_ans[i], int_ans[i - 1]) = (int_ans[i - 1], int_ans[i])
	if n % 2 == 1:
		int_ans.append(i + 2)
		(int_ans[-2], int_ans[-1]) = (int_ans[-1], int_ans[-2])
	print(*int_ans)


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


try:
	T = int(input())
	ans = []
	for _ in range(T):
		n = int(input())
		a = [0] * n
		for i in range(0, n, 2):
			a[i] = i + 2
			if i == n - 1:
				a[i] = a[i - 1]
				a[i - 1] = i + 1
			else:
				a[i + 1] = i + 1
		ans.append(a)
	for _ in range(T):
		print(' '.join(map(str, ans[_])))
except EOFError:
	pass


test_cases = int(input())
while test_cases > 0:
	n = int(input())
	list_nums = []
	for i in range(1, n // 2 + 1):
		list_nums.append(2 * i)
		list_nums.append(2 * i - 1)
	if n % 2 != 0:
		list_nums.append(n)
		(list_nums[-2], list_nums[-1]) = (list_nums[-1], list_nums[-2])
	print(*list_nums)
	test_cases -= 1


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


tests = int(input())
for t in range(tests):
	n = int(input())
	permut = '2'
	if n % 2 == 0:
		for i in range(2, n + 1):
			if i % 2 == 1:
				permut = permut + ' ' + str(i + 1)
			else:
				permut = permut + ' ' + str(i - 1)
		print(permut)
		pass
	elif n == 1:
		print(1)
		pass
	else:
		for i in range(2, n):
			if i % 2 == 1:
				permut = permut + ' ' + str(i + 1)
			else:
				permut = permut + ' ' + str(i - 1)
		edit_permut = permut[:-1]
		temp = permut[-1]
		edit_permut = edit_permut + str(n)
		edit_permut = edit_permut + ' ' + temp
		print(edit_permut)
		pass


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


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


for i in range(int(input())):
	n = int(input())
	a = list((int(x) for x in range(1, n + 1)))
	for j in range(1, n + 1):
		if a[j - 1] == j:
			if j < n:
				(a[j - 1], a[j]) = (a[j], a[j - 1])
			else:
				(a[j - 2], a[j - 1]) = (a[j - 1], a[j - 2])
	print(*a, sep=' ')


try:
	T = int(input())
	while T > 0:
		n = int(input())
		i = 1
		for j in range(n // 2 - 1):
			print(i + 1, i, end=' ')
			i += 2
		if n % 2 == 0:
			print(i + 1, i)
		else:
			print(i + 1, i + 2, i)
		T -= 1
except:
	pass


import sys

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

def Strs():
	return map(str, sys.stdin.readline().strip().split())

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

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

def Int():
	return int(sys.stdin.readline().strip())

def MOD():
	return 1000000007
t = Int()
while t:
	N = Int()
	ans = [i for i in range(1, N + 1)]
	i = 1
	while i < N:
		(ans[i], ans[i - 1]) = (ans[i - 1], ans[i])
		i += 2
	if N & 1:
		for i in range(1, N):
			if i + 1 == ans[i]:
				(ans[i], ans[i - 1]) = (ans[i - 1], ans[i])
	for i in ans:
		print(i, end=' ')
	print()
	t -= 1


t = int(input())
while t != 0:
	n = int(input())
	a = []
	for i in range(1, n + 1):
		a.append(i)
	for i in range(0, n - 1, 2):
		(a[i], a[i + 1]) = (a[i + 1], a[i])
	if n % 2 != 0:
		(a[n - 1], a[n - 2]) = (a[n - 2], a[n - 1])
	print(*a)
	t -= 1


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


for _ in range(int(input())):
	n = int(input())
	if n == 2:
		print(2, 1)
	elif n == 3:
		print(2, 3, 1)
	else:
		l = [0] * n
		(even, odd) = (2, 1)
		for i in range(n):
			if n % 2 == 1 and i == n - 1:
				temp = l[i - 1]
				l[i - 1] = odd
				l[i] = temp
			elif i & 1 == 1:
				l[i] = odd
				odd = odd + 2
			else:
				l[i] = even
				even = even + 2
		print(*l)


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