Let's define the value of the permutation $p$ of $n$ integers $1$, $2$, ..., $n$ (a permutation is an array where each element from $1$ to $n$ occurs exactly once) as follows:

initially, an integer variable $x$ is equal to $0$;

if $x < p_1$, then add $p_1$ to $x$ (set $x = x + p_1$), otherwise assign $0$ to $x$;

if $x < p_2$, then add $p_2$ to $x$ (set $x = x + p_2$), otherwise assign $0$ to $x$;

...

if $x < p_n$, then add $p_n$ to $x$ (set $x = x + p_n$), otherwise assign $0$ to $x$;

the value of the permutation is $x$ at the end of this process.

For example, for $p = [4, 5, 1, 2, 3, 6]$, the value of $x$ changes as follows: $0, 4, 9, 0, 2, 5, 11$, so the value of the permutation is $11$.

You are given an integer $n$. Find a permutation $p$ of size $n$ with the maximum possible value among all permutations of size $n$. If there are several such permutations, you can print any of them.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 97$) — the number of test cases.

The only line of each test case contains one integer $n$ ($4 \le n \le 100$).


-----Output-----

For each test case, print $n$ integers — the permutation $p$ of size $n$ with the maximum possible value among all permutations of size $n$.


-----Examples-----

Input
3
4
5
6
Output
2 1 3 4
1 2 3 4 5
4 5 1 2 3 6


-----Note-----

None

Source: codeforces | Difficulty: EASY
Tags: Greedy algorithms

Constructive algorithms


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


for _ in range(int(input())):
	n = int(input())
	res = []
	if n % 2 == 0:
		for i in range(n - 2, 0, -1):
			res.append(i)
		res.append(n - 1)
		res.append(n)
		print(' '.join((str(i) for i in res)))
		continue
	elif n % 2 == 1:
		res.append(1)
		for i in range(n - 2, 1, -1):
			res.append(i)
		res.append(n - 1)
		res.append(n)
		print(' '.join((str(i) for i in res)))
		continue


for _ in range(int(input())):
	n = int(input())
	s = ''
	if n % 2 == 0:
		for i in range(1, n - 1, 2):
			s += str(i + 1) + ' ' + str(i) + ' '
		s += ' ' + str(n - 1) + ' ' + str(n)
	else:
		A = [i for i in range(1, n + 1)]
		A.remove(1)
		A.remove(n - 2)
		A.remove(n)
		A.sort()
		for j in range(1, len(A), 2):
			s += str(A[j]) + ' ' + str(A[j - 1]) + ' '
		s += ' ' + str(1) + ' ' + str(n - 2) + ' ' + str(n)
	print(s)


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


class Solution:

	def solve(n: int):
		remainder = n % 2
		lst = []
		if remainder == 1:
			lst.append(str(remainder))
		for i in range(remainder + 1, n - 1, 2):
			lst.append(str(i + 1))
			lst.append(str(i))
		return ' '.join(lst + [str(n - 1), str(n)])

	def bestPermutation():
		n = int(input())
		for i in range(n):
			size = int(input())
			print(Solution.solve(size))
Solution.bestPermutation()


for i in range(int(input())):
	a = int(input())
	x = []
	if a == 4:
		print(2, 1, 3, 4)
	else:
		for j in range(2, a - 2):
			x.append(str(j))
		x = x[::-1]
		x.extend([str(a - 2), '1', str(a - 1), str(a)])
		print(' '.join(x))


t = int(input())
for _ in range(t):
	n = int(input())
	print('1 ' * (n % 2) + ' '.join(map(str, range(n - 2, n % 2, -1))) + f' {n - 1} {n}')


import sys, math
input = sys.stdin.readline
INF = int(1000000000.0) + 7
MOD = 998244353

def solve():
	n = int(input())
	result = [0] * n
	result[-1] = n
	result[-2] = n - 1
	e = n - 2
	s = 1
	if n % 2 == 0:
		for i in range(n - 2):
			if i % 2 == 0:
				result[i] = e
				e -= 1
			else:
				result[i] = s
				s += 1
	else:
		for i in range(n - 2):
			if i % 2 == 0:
				result[i] = s
				s += 1
			else:
				result[i] = e
				e -= 1
	print(*result)
t = 1
t = int(input())
for i in range(1, t + 1):
	solve()


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


for jj in range(int(input())):
	n = int(input())
	if n % 2 == 0:
		t = list(range(1, n - 1))
		print(*t[::-1] + [n - 1, n])
	elif n == 5:
		print(*[1, 2, 3, 4, 5])
	else:
		print(*[1, 2, 3] + list(range(4, n - 1))[::-1] + [n - 1, n])


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


for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(1)
	elif n == 2:
		print(1, 2)
	elif n == 3:
		print(2, 1, 3)
	elif n % 2:
		print(1, 2, 3, *range(n - 2, 3, -1), n - 1, n)
	else:
		print(*range(n - 2, 0, -1), n - 1, n)


import sys

def solve():
	inp = sys.stdin.readline
	n = int(inp())
	if n % 2 == 0:
		a = list(range(n - 2, 0, -1)) + [n - 1, n]
	else:
		a = [n - 3, n - 2] + list(range(n - 4, 0, -1)) + [n - 1, n]
	print(' '.join(map(str, a)))

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


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

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

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

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

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
t = inp()
for _ in range(t):
	n = inp()
	if n % 2 == 0:
		for i in range(n - 2):
			if i % 2 == 0:
				print(i + 2, end=' ')
			else:
				print(i, end=' ')
		print(n - 1, n)
	else:
		print(1, 2, 3, end=' ')
		for i in range(4, n - 2 + 1):
			if i % 2 == 0:
				print(i + 1, end=' ')
			else:
				print(i - 1, end=' ')
		print(n - 1, n)


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


from collections import *
for _ in range(int(input())):
	n = int(input())
	ans = []
	if n % 2:
		ans += [1]
		for i in range(2, n - 1, 2):
			ans += [i + 1, i]
	else:
		for i in range(1, n - 1, 2):
			ans += [i + 1, i]
	ans += [n - 1, n]
	print(*ans)


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


t = int(input())
ans = []
for _ in range(t):
	n = int(input())
	s = ''
	if n == 1:
		ans.append('1')
		continue
	l1 = list(range(n - 2, 0, -1))
	if n % 2 == 1:
		l1 = [1, 2, 3] + l1[:-3]
	l2 = [n - 1, n]
	for i in l1:
		s += str(i) + ' '
	for i in l2:
		s += str(i) + ' '
	ans.append(s)
for i in ans:
	print(i[:-1])


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


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


for _ in range(int(input())):
	n = int(input())
	if n == 4:
		print(2, 1, 3, 4)
	else:
		l = [i for i in range(1, n + 1)]
		ans = [2, 3, 1, n - 1, n]
		res = []
		for j in l:
			if j not in ans:
				res.append(j)
		res += ans
		print(*res)


t = int(input())
for _ in range(t):
	n = int(input())
	l = [str(i) for i in range(1, n + 1)]
	if len(l) <= 2:
		print(' '.join(l))
	elif len(l) == 3:
		print('2 1 3')
	else:
		i = 0
		if (n - 2) % 2 == 1:
			i = 3
		while i < n - 2:
			temp = l[i]
			l[i] = l[i + 1]
			l[i + 1] = temp
			i += 2
		print(' '.join(l))


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


t = int(input())
for _ in range(t):
	(n,) = map(int, input().split())
	a = [0] * n
	if n % 2 == 0:
		for i in range(1, n - 1):
			a[i - 1] = n - i - 1
	else:
		for i in range(3):
			a[i] = i + 1
		for i in range(4, n - 1):
			a[i - 1] = n - i + 2
	a[-2] = n - 1
	a[-1] = n
	print(*a)


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


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


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	ans1 = [i for i in range(1, n - 1)][::-1] + [n - 1, n]
	ans2 = [1] + [i for i in range(2, n - 1)][::-1] + [n - 1, n]
	return ans1 if n % 2 == 0 else ans2
for _ in range(int(input())):
	print(*solve())


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


for _ in range(int(input())):
	n = int(input())
	if n % 2 == 0:
		a = [i for i in range(1, n - 1)]
		a.sort(reverse=True)
		a.append(n - 1)
		a.append(n)
		print(*a)
	else:
		a = [i for i in range(1, n - 4)]
		a.sort(reverse=True)
		a.append(n - 4)
		a.append(n - 3)
		a.append(n - 2)
		a.append(n - 1)
		a.append(n)
		print(*a)


def solve(n):
	if n == 4:
		return [2, 1, 3, 4]
	if n == 5:
		return [1, 2, 3, 4, 5]
	if n % 2:
		return [1] + list(range(n - 2, 1, -1)) + [n - 1, n]
	else:
		return list(range(n - 2, 0, -1)) + [n - 1, n]
for _ in range(int(input())):
	print(*solve(int(input())))


t = int(input())
while t:
	n = int(input())
	res = [0 for i in range(n)]
	res[n - 1] = n
	res[n - 2] = n - 1
	res[n - 3] = 1
	res[n - 4] = 3
	res[n - 5] = 2
	if n > 5:
		for i in range(n - 5):
			res[i] = i + 4
	if n == 4:
		res = [2, 1, 3, 4]
	print(*res)
	t -= 1


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


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


import sys
input = sys.stdin.readline

def print(*args, end='\n', sep=' ') -> None:
	sys.stdout.write(sep.join(map(str, args)) + end)

def Solve():
	for t in range(int(input())):
		n = int(input())
		ans = [i for i in range(1, n + 1)]
		if n % 3 == 0:
			(ans[0], ans[1]) = (ans[1], ans[0])
		(ans[~2], ans[~3]) = (ans[~3], ans[~2])
		print(*ans)
Solve()


t = int(input())
for i in range(t):
	n = int(input())
	a = [0] * n
	if n == 4:
		print('2 1 3 4')
	else:
		for i in range(n - 5):
			print(i + 4, end=' ')
		print('2 3 1', end=' ')
		print(n - 1, n)


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


t = int(input())
while t:
	n = int(input())
	if n % 3 == 0:
		a = [x for x in range(n - 3, 1, -1)]
		a += [n - 2, 1, n - 1, n]
		print(*a)
	else:
		a = [x for x in range(2, n + 1)]
		a.insert(n - 3, 1)
		print(*a)
	t -= 1


import math
import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	res = 1
	lst = []
	if n % 2:
		lst.append(1)
		for i in reversed(range(2, n - 1)):
			lst.append(i)
	else:
		for i in reversed(range(n - 2)):
			lst.append(i + 1)
	lst = lst + [n - 1, n]
	for i in lst:
		print(i, end=' ')
	print()
t = int(input())
while t:
	t -= 1
	solve()


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


t = int(input())
for i in range(t):
	n = int(input())
	if n == 4:
		print(2, 1, 3, 4)
		continue
	a = []
	for i in range(4, n - 1):
		a.append(i)
	a.append(2)
	a.append(3)
	a.append(1)
	a.append(n - 1)
	a.append(n)
	print(*a)


t = eval(input())
for i in range(t):
	n = eval(input())
	d = []
	if n % 2 == 0:
		(l, r) = (2, 1)
		for i in range(n // 2 - 1):
			d.append(l)
			d.append(r)
			l += 2
			r += 2
		d.append(n - 1)
		d.append(n)
		print(*d)
	else:
		d.append(1)
		d.append(2)
		d.append(3)
		(l, r) = (5, 4)
		for i in range((n - 5) // 2):
			d.append(l)
			d.append(r)
			l += 2
			r += 2
		d.append(n - 1)
		d.append(n)
		print(*d)


import sys
import math

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

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

def test_ok(ok):
	print('YES' if ok else 'NO')

def main():
	for _ in range(int(input())):
		n = int(input())
		if n == 5:
			for i in range(n):
				print(i + 1, end=' ')
			print()
			continue
		if n % 2 == 0:
			for i in range(n - 2, 0, -1):
				print(i, end=' ')
			print(n - 1, n)
		else:
			a = (n - 1) // 2 - 1
			b = a + 2
			ans = [a, b, n]
			for i in range(n - 1, 0, -1):
				if i not in ans:
					print(i, end=' ')
			print(*ans)
main()


import sys
input = sys.stdin.readline
tests = int(input())
for test in range(tests):
	n = int(input())
	if n % 2:
		for tal in reversed(range(n - 5)):
			print(tal + 4, end=' ')
		print(1, end=' ')
		print(2, end=' ')
		print(3, end=' ')
		print(n - 1, end=' ')
		print(n)
	else:
		for tal in reversed(range(n - 2)):
			print(tal + 1, end=' ')
		print(n - 1, end=' ')
		print(n)


import sys
t = int(input())
while t:
	p = int(input())
	if p % 2:
		s = [i for i in range(p - 3, 1, -1)]
		s.append(p - 2)
		s.append(1)
		s.append(p - 1)
		s.append(p)
		print(*s)
	else:
		s = [i for i in range(p - 2, 0, -1)]
		s.append(p - 1)
		s.append(p)
		print(*s)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	d = {}
	a = []
	if n % 2 == 0:
		for i in range(n - 2, 0, -1):
			print(i, end=' ')
		print(n - 1, end=' ')
		print(n, end=' ')
		print()
	else:
		a.append(n)
		a.insert(0, n // 2 + 1)
		a.insert(0, a[0] - 2)
		for i in range(1, n):
			if i not in a:
				a.insert(0, i)
		for i in a:
			print(i, end=' ')
		print()


for _ in range(int(input())):
	a = int(input())
	ans = [0] * a
	ans_str = ''
	if a == 4:
		ans_str = '2' + ' ' + '1' + ' ' + '3' + ' ' + '4'
	else:
		ans[-3] = 1
		ans[-4] = 3
		ans[-5] = 2
		ans[-1] = a
		ans[-2] = a - 1
		for z in range(0, a - 5):
			ans[z] = z + 4
		for i in ans:
			ans_str += str(i) + ' '
	print(ans_str)


t = int(input())
for e in range(t):
	n = int(input())
	a = []
	if n == 4:
		a = [2, 1, 3, 4]
		print(*a)
	elif n % 2 != 0:
		a = [1, 2, 3]
		q = 5
		while q < n - 1:
			a.append(q)
			a.append(q - 1)
			q += 2
		a.append(n - 1)
		a.append(n)
		print(*a)
	else:
		q = 2
		while q < n - 1:
			a.append(q)
			a.append(q - 1)
			q += 2
		a.append(n - 1)
		a.append(n)
		print(*a)


import sys
import math
from collections import Counter

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

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

def fun(a):
	a = [i for i in range(1, a + 1)]
	i = 0
	l = len(a)
	ans = []
	j = l - 3
	while i <= j:
		ans.append(a[i])
		if i != j:
			ans.append(a[j])
		i += 1
		j -= 1
	ans = ans[::-1]
	ans.append(l - 1)
	ans.append(l)
	return ans
for _ in range(int(input())):
	x = input()
	print(*fun(int(x)))


t = int(input())
for i in range(t):
	n = int(input())
	if n % 2 == 0:
		arr = list(range(1, n - 1))
		for i in range(0, n - 2, 2):
			(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
		arr.append(n - 1)
		arr.append(n)
	if n % 2 == 1:
		arr = list(range(2, n))
		arr.remove(n - 2)
		for i in range(0, n - 3, 2):
			(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
		arr.append(1)
		arr.append(n - 2)
		arr.append(n)
	print(*arr)


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


try:
	for _ in range(int(input())):
		n = int(input())
		l = []
		for i in range(n - 2, 0, -1):
			l.append(i)
		if n % 2 != 0:
			tem = l[0]
			l[0] = l[1]
			l[1] = tem
		l.append(n - 1)
		l.append(n)
		for i in range(n):
			print(l[i], end=' ')
		print()
except:
	pass


for _ in range(int(input())):
	a = []
	n = int(input())
	if 'erfjijferjr32r32r32' == 232434323235566:
		print('Tanmay')
	if n & 1:
		for i in range(n):
			if i % 2 == 1:
				a.append(i + 2)
				continue
			a.append(i)
		a[0] = 1
	else:
		for i in range(n):
			if i % 2 == 0:
				a.append(i + 2)
				continue
			a.append(i)
	a[n - 1] = n
	a[n - 2] = n - 1
	for i in a:
		print(i, end=' ')
	print()


def solveOne():
	n = int(input())
	return (list(range(1, n - 1)[::-1]) if n % 2 == 0 else [1] + list(range(2, n - 1)[::-1])) + [n - 1, n]

def countX(nums):
	x = 0
	for numsEl in nums:
		if x < numsEl:
			x += numsEl
		else:
			x = 0
	return x

def solve():
	t = int(input())
	anss = []
	for _ in range(t):
		anss.append(solveOne())
	for ans in anss:
		print(*ans)
solve()


t = int(input())
for i in range(t):
	n = int(input())
	AN = [n - 1, n]
	if n % 2 == 0:
		A = []
		for i in range(n - 2):
			A.append(n - 2 - i)
		ANS = A + AN
	else:
		B = [1, 2, 3]
		A = []
		for i in range(4, n - 1):
			A.append(n - 2 - i + 4)
		ANS = B + A + AN
	for i in range(len(ANS)):
		if i < len(ANS) - 1:
			print(ANS[i], end=' ')
		else:
			print(ANS[i])


for ax in range(int(input())):
	a = int(input())
	arr = []
	x = 0
	for i in range(2, a - 1):
		arr.append(i)
		if x < i:
			x = x + i
		else:
			x = 0
	if x == 0:
		arr[0] = a - 2
		arr[-1] = 2
	arr.append(1)
	arr.append(a - 1)
	arr.append(a)
	print(*arr)


def FindValue(x):
	ans = 0
	for i in range(len(x)):
		if ans < x[i]:
			ans += x[i]
		else:
			ans = 0
	return ans
for _ in range(int(input())):
	n = int(input())
	a = []
	if n % 2 == 1:
		a = [1, 2, 3]
		for i in range(n - 2, 3, -1):
			a.append(i)
		a += [n - 1, n]
	else:
		for i in range(n - 2, 0, -1):
			a.append(i)
		a.append(n - 1)
		a.append(n)
	for i in a:
		print(i, end=' ')
	print('')


t = int(input())
while t > 0:
	b = int(input())
	out = [None for i in range(b)]
	if b % 2 == 0:
		for i in range(b - 2):
			out[i] = b - i - 2
		out[b - 2] = b - 1
		out[b - 1] = b
	else:
		out[0] = 1
		for i in range(1, b - 2):
			out[i] = b - i - 1
		out[b - 2] = b - 1
		out[b - 1] = b
	for i in out:
		print(i, end=' ')
	print()
	t -= 1


for _ in range(int(input())):
	n = int(input())
	if n & 1:
		val = n - 4
		arr = [x for x in range(val, 0, -1)]
		for i in range(val + 1, n + 1):
			arr.append(i)
		print(*arr)
	else:
		val = n - 2
		arr = [x for x in range(val, 0, -1)]
		for i in range(val + 1, n + 1):
			arr.append(i)
		print(*arr)


class Solution:

	def bestPermutation(self, n):
		if n % 2 == 1:
			if n == 5:
				return ' '.join([str(i) for i in range(1, 6)])
			arr = set((i for i in range(1, n + 1)))
			res_back = [2, n - 3, n]
			for i in res_back:
				arr.remove(i)
			res = [i for i in sorted(arr)]
			return ' '.join(map(str, res[::-1] + res_back))
		return ' '.join([str(i) for i in range(n - 2, 0, -1)] + [str(n - 1), str(n)])
ob = Solution()
t = int(input())
while t:
	n = int(input())
	print(ob.bestPermutation(n))
	t -= 1


n = int(input())
for j in range(n):
	x = int(input())
	a = [k + 1 for k in range(x)]
	if x % 2 == 0:
		a.pop(x - 1)
		a.pop(x - 2)
		b = a[::-1]
		print(' '.join(map(str, b)), x - 1, x)
	else:
		a.pop(x - 1)
		a.pop(x - 3)
		a.pop(0)
		b = a[::-1]
		print(' '.join(map(str, b)), 1, x - 2, x)


test = int(input())
for t in range(test):
	n = int(input())
	if n % 2 == 0:
		num = list(range(1, n - 1))
		num.reverse()
		num.append(n - 1)
		num.append(n)
		print(*num)
	else:
		num = list(range(2, n - 1))
		num.reverse()
		num.insert(0, 1)
		num.append(n - 1)
		num.append(n)
		print(*num)


tt = int(input())
for t in range(tt):
	n = int(input())
	a = [0] * n
	a[n - 1] = n
	a[n - 2] = n - 1
	i = 1
	for e in range(n - 3, -1, -1):
		a[e] = i
		i += 1
	if n % 2 == 1:
		(a[0], a[1]) = (a[1], a[0])
	for i in a:
		print(i, end=' ')
	print()


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


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


t = int(input())
for e in range(t):
	n = int(input())
	data = list(range(1, n + 1))
	if n % 2 == 0:
		print(' '.join(map(str, list(reversed(data[:n - 2])) + data[n - 2:])))
	else:
		print('1 2 3 ' + ' '.join(map(str, list(reversed(data[3:n - 2])) + data[n - 2:])))


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


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


t = int(input())
for i in range(t):
	a = int(input())
	l = [2, 1, 3, 4]
	if a == 4:
		print(*l)
	else:
		l1 = [0] * a
		l1[a - 1] = a
		l1[a - 2] = a - 1
		l1[a - 3] = 1
		l1[a - 4] = 3
		l1[a - 5] = 2
		for j in range(a - 5):
			l1[j] = j + 4
		print(*l1)


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


def func(n):
	arr = [0 for _ in range(n)]
	if n % 2 == 1:
		arr[n - 1] = n
		arr[n - 2] = n - 1
		arr[n - 3] = 1
		arr[n - 4] = n - 2
		arr[n - 5] = n - 3
		i = 0
		for d in range(n - 4, 1, -1):
			arr[i] = d
			i += 1
	else:
		arr[n - 1] = n
		arr[n - 2] = n // 2
		arr[n - 3] = n // 2 - 1
		arr[n - 4] = 1
		arr[n - 5] = n - 2
		arr[n - 6] = n - 3
		arr[0] = n - 1
		i = 1
		d = n - 4
		while d != 1:
			arr[i] = d
			i += 1
			d -= 1
			if d == n // 2:
				d -= 2
	return arr
pmap = {}
pmap[4] = [2, 1, 3, 4]
pmap[5] = [1, 2, 3, 4, 5]
pmap[6] = [4, 5, 1, 2, 3, 6]
pmap[7] = [2, 3, 4, 5, 1, 6, 7]
pmap[8] = [6, 5, 4, 3, 2, 1, 7, 8]
pmap[9] = [5, 4, 3, 2, 6, 7, 1, 8, 9]
T = int(input())
for tc in range(T):
	n = int(input())
	if n in pmap:
		print(' '.join([str(elem) for elem in pmap[n]]))
	else:
		pmap[n] = func(n)
		print(' '.join([str(elem) for elem in pmap[n]]))


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


output = ''
for caseno in range(int(input())):
	totn = int(input())
	answer = ''
	if totn > 2:
		n = totn - 2
		if n % 2:
			l = [1] + [i + 1 for i in range(1, n)][::-1]
			answer += '1 '
			for i in range(1, n)[::-1]:
				answer += str(i + 1) + ' '
		else:
			l = [i + 1 for i in range(n)][::-1]
			for i in range(n)[::-1]:
				answer += str(i + 1) + ' '
		l += [totn - 1, totn]
		answer += str(totn - 1) + ' '
		answer += str(totn) + ' '
	else:
		answer = ''
		for i in range(n):
			answer += str(i + 1) + ' '
	x = 0
	output += str(answer) + '\n'
print(output)


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


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


def solution(n):
	s = ''
	if n % 2 == 0:
		for i in range(2, n - 1, 2):
			s += str(i) + ' ' + str(i - 1) + ' '
	else:
		s = '1 2 3 '
		for i in range(5, n - 1, 2):
			s += str(i) + ' ' + str(i - 1) + ' '
	s += str(n - 1) + ' ' + str(n)
	return s
t = int(input())
while t:
	n = int(input())
	print(solution(n))
	t -= 1


t = int(input())
for g in range(t):
	n = int(input())
	if n % 2 == 0:
		a = [0] * n
		a[-1] = n
		a[-2] = n - 1
		s = n - 2
		for i in range(n - 2):
			a[i] = s
			s -= 1
		print(*a)
	elif n % 3 == 0:
		a = [0] * n
		a[-1] = n
		a[-2] = n - 2
		a[-3] = 1
		a[0] = n - 1
		if (n - 3) % 2 == 0:
			s = n - 3
			for i in range(1, n - 3):
				a[i] = s
				s -= 1
			print(*a)
		else:
			s = 2
			for i in range(1, n - 3):
				a[i] = s
				s += 1
			print(*a)
	elif n % 6 == 1:
		a = [0] * n
		a[-1] = n
		a[-2] = n - 2
		a[-3] = 1
		a[0] = n - 1
		s = n - 3
		for i in range(1, n - 3):
			a[i] = s
			s -= 1
		print(*a)
	else:
		a = [0] * n
		a[-1] = n
		a[-2] = n - 1
		s = 1
		for i in range(n - 2):
			a[i] = s
			s += 1
		print(*a)


t = int(input())
for r in range(t):
	n = int(input())
	l = [i for i in range(1, n + 1)]
	if n % 3 == 1:
		if n - 2 > 0:
			(l[n - 4], l[n - 3]) = (l[n - 3], l[n - 4])
	if n % 6 == 0:
		l[:n - 2] = l[:n - 2][::-1]
	if n % 3 == 0 and n % 2 != 0:
		l = [0] + l
		(l[n // 2 + 1], l[-2]) = (l[-2], l[n // 2 + 1])
		(l[n // 2 - 1], l[-3]) = (l[-3], l[n // 2 - 1])
		l.pop(0)
	p = [0] * (len(l) + 1)
	print(''.join([str(a) + ' ' for a in l]))


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


for _ in range(int(input())):
	n = int(input())
	p = []
	if n & 1:
		p.append(n // 2)
	i = n - 2
	j = 1
	while i > j:
		p.append(i)
		p.append(j)
		i = i - 1
		j = j + 1
	p.append(n - 1)
	p.append(n)
	print(*p)


from functools import lru_cache
t = int(input())
for _ in range(t):
	n = int(input())
	if n % 2 == 0:
		res = [i for i in range(1, n - 1)][::-1] + [n - 1, n]
	else:
		res = [i for i in range(2, n - 3)][::-1] + [1, n - 3, n - 2] + [n - 1, n]
	print(*res)


for _ in range(int(input())):
	a = []
	n = int(input())
	if n == 4:
		a = [2, 1, 3, 4]
	elif n == 5:
		a = [2, 3, 1, 4, 5]
	else:
		a = [2, 3, 1, n - 1, n]
	b = []
	for i in range(n - 5):
		b.append(i + 4)
	a = b + a
	for i in a:
		print(i, end=' ')
	print()


t = int(input())
for k in range(t):
	n = int(input())
	b = []
	if n % 2 == 0:
		for i in range(1, n - 1):
			if i % 2 == 1:
				b += [i + 1]
			else:
				b += [i - 1]
		b += [n - 1]
		b += [n]
	elif n % 2 == 1:
		b += [1]
		b += [2]
		b += [3]
		for i in range(4, n - 1):
			if i % 2 == 0:
				b += [i + 1]
			else:
				b += [i - 1]
		b += [n - 1]
		b += [n]
	print(*b)


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


no_of_cases = int(input())
a = no_of_cases
ques = []
while a > 0:
	ques.append(int(input()))
	a = a - 1

def finder(a):
	b = a - 2
	ans = []
	if a % 2 == 0:
		while b > 0:
			ans.append(b)
			b = b - 1
	elif a % 2 == 1:
		ans.append(b - 1)
		ans.append(b)
		b = b - 2
		while b > 0:
			ans.append(b)
			b = b - 1
	ans.append(a - 1)
	ans.append(a)
	str1 = ''
	for ele in ans:
		ele = str(ele)
		str1 += ele + ' '
	return str1
for i in ques:
	print(finder(i))


import sys
sys.setrecursionlimit(200000)
import math
from collections import Counter
from collections import defaultdict
from collections import deque
input = sys.stdin.readline
from functools import lru_cache
import heapq

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())
testcases = inp()
for j in range(testcases):
	n = inp()
	x = deque()
	if n % 2 == 0:
		for i in range(n - 2, 0, -1):
			x.append(i)
		x.append(n - 1)
		x.append(n)
	else:
		for i in range(n - 2, 1, -1):
			x.append(i)
		x.append(n - 1)
		x.append(n)
		x.appendleft(1)
	print(*x)


n = int(input())
for i in range(n):
	m = int(input())
	if m % 3 == 2:
		for j in range(1, m + 1):
			if j != m:
				print(j, end=' ')
			else:
				print(j)
	elif m % 3 == 1:
		print('2 1 3', end=' ')
		for j in range(4, m + 1):
			if j != m:
				print(j, end=' ')
			else:
				print(j)
	else:
		print('1 2 4 3', end=' ')
		for j in range(5, m + 1):
			if j != m:
				print(j, end=' ')
			else:
				print(j)


def solution():
	n = int(input())
	res = list()
	if n % 2 == 0:
		for i in range(n - 2, 0, -1):
			res.append(i)
		res.append(n - 1)
		res.append(n)
		print(*res)
	else:
		for i in range(n - 3, 0, -1):
			res.append(i)
		res.insert(len(res) - 1, n - 2)
		res.append(n - 1)
		res.append(n)
		print(*res)
t = int(input())
while t:
	t -= 1
	solution()


for i in range(int(input())):
	l = []
	x = int(input())
	if x == 1:
		print(1)
	elif x == 2:
		print('1 2')
	elif x == 3:
		print(1, 2, 3)
	elif x % 2 == 0:
		s = 1
		e = x - 2
		for i in range((x - 1) // 2):
			l.append(str(s))
			l.append(str(e))
			s += 1
			e -= 1
		l.reverse()
		l.extend([str(x - 1), str(x)])
		print(' '.join(l))
	elif x % 2 != 0:
		s = 1
		e = x - 2
		y = (x + 1) // 2
		for i in range((x - 2) // 2):
			if e == y:
				e -= 1
			if s == y:
				s += 1
			l.append(str(e))
			l.append(str(s))
			s += 1
			e -= 1
		l.reverse()
		l.extend([str(y), str(x - 1), str(x)])
		print(' '.join(l))


import sys
import heapq
input = sys.stdin.readline
from collections import Counter, defaultdict

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

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

def main():
	n = inp()
	if n % 2 == 0:
		ans = [x for x in range(n - 2, 0, -1)] + [n - 1, n]
	else:
		ans = [1] + [x for x in range(n - 2, 1, -1)] + [n - 1, n]
	print(*ans)
t = inp()
for _ in range(t):
	main()