A permutation of length $n$ is a sequence of integers from $1$ to $n$ such that each integer appears in it exactly once.

Let the fixedness of a permutation $p$ be the number of fixed points in it — the number of positions $j$ such that $p_j = j$, where $p_j$ is the $j$-th element of the permutation $p$.

You are asked to build a sequence of permutations $a_1, a_2, \dots$, starting from the identity permutation (permutation $a_1 = [1, 2, \dots, n]$). Let's call it a permutation chain. Thus, $a_i$ is the $i$-th permutation of length $n$.

For every $i$ from $2$ onwards, the permutation $a_i$ should be obtained from the permutation $a_{i-1}$ by swapping any two elements in it (not necessarily neighboring). The fixedness of the permutation $a_i$ should be strictly lower than the fixedness of the permutation $a_{i-1}$.

Consider some chains for $n = 3$:

$a_1 = [1, 2, 3]$, $a_2 = [1, 3, 2]$ — that is a valid chain of length $2$. From $a_1$ to $a_2$, the elements on positions $2$ and $3$ get swapped, the fixedness decrease from $3$ to $1$.

$a_1 = [2, 1, 3]$, $a_2 = [3, 1, 2]$ — that is not a valid chain. The first permutation should always be $[1, 2, 3]$ for $n = 3$.

$a_1 = [1, 2, 3]$, $a_2 = [1, 3, 2]$, $a_3 = [1, 2, 3]$ — that is not a valid chain. From $a_2$ to $a_3$, the elements on positions $2$ and $3$ get swapped but the fixedness increase from $1$ to $3$.

$a_1 = [1, 2, 3]$, $a_2 = [3, 2, 1]$, $a_3 = [3, 1, 2]$ — that is a valid chain of length $3$. From $a_1$ to $a_2$, the elements on positions $1$ and $3$ get swapped, the fixedness decrease from $3$ to $1$. From $a_2$ to $a_3$, the elements on positions $2$ and $3$ get swapped, the fixedness decrease from $1$ to $0$.

Find the longest permutation chain. If there are multiple longest answers, print any of them.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 99$) — the number of testcases.

The only line of each testcase contains a single integer $n$ ($2 \le n \le 100$) — the required length of permutations in the chain.


-----Output-----

For each testcase, first, print the length of a permutation chain $k$.

Then print $k$ permutations $a_1, a_2, \dots, a_k$. $a_1$ should be an identity permutation of length $n$ ($[1, 2, \dots, n]$). For each $i$ from $2$ to $k$, $a_i$ should be obtained by swapping two elements in $a_{i-1}$. It should also have a strictly lower fixedness than $a_{i-1}$.


-----Examples-----

Input
2
2
3
Output
2
1 2
2 1
3
1 2 3
3 2 1
3 1 2


-----Note-----

None

Source: codeforces | Difficulty: EASY
Tags: Mathematics

Constructive algorithms


Solutions:
def troca(arr, i, j):
	aux = arr[j]
	arr[j] = arr[i]
	arr[i] = aux
	return arr

def permutation(n):
	arr = [str(i) for i in range(1, n + 1)]
	print(' '.join(arr))
	troca(arr, len(arr) - 1, 0)
	print(' '.join(arr))
	if len(arr) > 2:
		for i in range(len(arr) - 1, 1, -1):
			troca(arr, i, i - 1)
			print(' '.join(arr))

def main():
	n = int(input())
	for i in range(n):
		el = int(input())
		print(el)
		permutation(el)
main()


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


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


def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		nums = [str(i) for i in range(1, n + 1)]
		print(n)
		print(' '.join(nums))
		for i in range(n - 1):
			(nums[i], nums[i + 1]) = (nums[i + 1], nums[i])
			print(' '.join(nums))
main()


t = int(input())
for i in range(t):
	n = int(input())
	a = []
	print(n)
	for k in range(1, n + 1):
		a.append(str(k))
	j = 0
	while j < n - 1:
		print(' '.join(a))
		(a[j], a[j + 1]) = (a[j + 1], a[j])
		j += 1
	print(' '.join(a))


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


for _ in range(int(input())):
	n = int(input())
	out = [str(nn) for nn in range(1, n + 1)]
	print(n)
	print(' '.join(out))
	for x in range(1, n):
		(out[x], out[0]) = (out[0], out[x])
		print(' '.join(out))


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


t = int(input())
for i in range(t):
	numberPermutation = int(input())
	permutation = list(map(str, range(1, numberPermutation + 1)))
	text = ' '.join(permutation)
	print(numberPermutation)
	print(text)
	for j in range(numberPermutation - 1):
		(permutation[j], permutation[j + 1]) = (permutation[j + 1], permutation[j])
		text = ' '.join(permutation)
		print(text)


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


for i in range(int(input())):
	num = int(input())
	lis = [str(x) for x in list(range(1, num + 1))]
	line = []
	line.append(' '.join(lis))
	(lis[0], lis[-1]) = (lis[-1], lis[0])
	line.append(' '.join(lis))
	first = 1
	last = -1
	for x in range(num - 2):
		(lis[first], lis[last]) = (lis[last], lis[first])
		line.append(' '.join(lis))
		last -= 1
	print(num)
	for x in line:
		print(x)


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


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


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


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


t = int(input())
for i in range(t):
	n = int(input())
	print(n)
	a = []
	for k in range(n):
		a.append(str(k + 1))
	for k in range(n):
		s = ' '.join(a)
		print(s)
		if k != n - 1:
			x = a[k]
			a[k] = a[k + 1]
			a[k + 1] = x


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


x = int(input())

def cal(n):
	t = []
	p = [str(i) for i in range(1, n + 1)]
	t.append(p)
	for i in range(n - 1):
		k = t[-1][:]
		(k[i], k[n - 1]) = (k[n - 1], k[i])
		t.append(k)
	return t
for jj in range(x):
	n = int(input())
	a = cal(n)
	print(n)
	for i in range(n):
		print(' '.join(a[i]))


trials = int(input())
answer_list = []
for _ in range(trials):
	i = int(input())
	answer_list.append(i)
	x = i - 2
	li = []
	for d in range(i):
		li.append(str(d + 1))
	answer_list.append(' '.join(li))
	index = -1
	while x >= 0:
		index += 1
		j = li[index]
		li[index] = li[index + 1]
		li[index + 1] = j
		answer_list.append(' '.join(li))
		x -= 1
for g in answer_list:
	print(g)


T = int(input())
for i in range(T):
	N = int(input())
	print(N)
	lis = [str(x) for x in range(1, N + 1)]
	string = ' '.join(lis)
	print(string)
	for i in range(0, N - 1):
		(lis[i], lis[i + 1]) = (lis[i + 1], lis[i])
		string = ' '.join(lis)
		print(string)


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


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


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


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


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


t = int(input())
for i in range(0, t):
	n = int(input())
	if n != 1:
		answer = n
	else:
		answer = 1
	print(answer)
	l = []
	for j in range(0, n):
		l.append(str(j + 1))
	print(' '.join(l))
	if n == 1:
		continue
	else:
		for k in range(0, n - 1):
			(l[k], l[k + 1]) = (l[k + 1], l[k])
			print(' '.join(l))


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


t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	arr = [str(i + 1) for i in range(n)]
	print(n)
	for i in range(n):
		print(' '.join(arr))
		if i == n - 1:
			break
		(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])


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


def solve(n):
	print(n)
	ans = list(map(str, range(1, n + 1)))
	print(' '.join(ans))
	(ans[0], ans[-1]) = (ans[-1], ans[0])
	p1 = n - 1
	for i in range(n - 1):
		print(' '.join(ans))
		(ans[p1], ans[p1 - 1]) = (ans[p1 - 1], ans[p1])
		p1 -= 1
	return 0
for _ in range(int(input())):
	n = int(input())
	solve(n)


t = int(input())
for i in range(t):
	n = int(input())
	permutation = [str(i) for i in range(1, n + 1)]
	print(n)
	for j in range(n - 1, -1, -1):
		begin = permutation[0:j]
		end = permutation[j:n - 1]
		print(' '.join(begin) + (' ' if len(begin) > 0 else '') + str(n) + (' ' if len(end) > 0 else '') + ' '.join(end))


def get(n):
	print(n)
	l = []
	for x in range(1, n + 1):
		l.append(str(x))
	p = len(l)
	print(stri(l))
	i = 0
	while i < p - 1:
		(l[i], l[i + 1]) = (l[i + 1], l[i])
		print(stri(l))
		i = i + 1

def stri(l):
	str1 = ''
	for ele in l:
		str1 += ele + ' '
	return str1
t = int(input())
for i in range(t):
	n = int(input())
	get(n)


from typing import List
n = int(input())

def printArray(array: List[int]):
	print(str(array).replace(',', '').replace('[', '').replace(']', ''))

def printlongChain(size: int):
	array = [i + 1 for i in range(size)]
	printArray(array)
	for i in range(size - 1):
		aux = array[i]
		array[i] = array[-1]
		array[-1] = aux
		printArray(array)
for i in range(n):
	size = int(input())
	print(size)
	printlongChain(size)


t = int(input())
for i in range(t):
	n = int(input())
	print(n)
	seq = []
	for j in range(n):
		seq.append(str(j + 1))
	print(' '.join(map(str, seq)))
	for j in range(n, 1, -1):
		(seq[j - 1], seq[j - 2]) = (seq[j - 2], seq[j - 1])
		print(' '.join(map(str, seq)))


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


test_cases = int(input())
k = 1
while k <= test_cases:
	permutation_number = int(input())
	print(permutation_number)
	i = 1
	S = [t + 1 for t in range(permutation_number)]
	betterlist = ' '.join((repr(item) for item in S))
	print(betterlist)
	while i < permutation_number:
		S.pop(i)
		S.pop(0)
		S.insert(0, i + 1)
		S.insert(i, i)
		betterlist = ' '.join((repr(item) for item in S))
		print(betterlist)
		i += 1
	k += 1


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()
	a = [i for i in range(1, n + 1)]
	print(n)
	print(' '.join(map(str, a)))
	(a[0], a[-1]) = (a[-1], a[0])
	for i in range(n - 1):
		print(' '.join(map(str, a)))
		(a[i], a[i + 1]) = (a[i + 1], a[i])


import sys
input = sys.stdin.readline

def print(*args, end='\n', sep=' ') -> None:
	sys.stdout.write(sep.join(map(str, args)) + end)
N = []
for t in range(int(input())):
	N.append(int(input()))
for n in N:
	print(n)
	a = [i for i in range(1, n + 1)]
	print(*a)
	for i in range(n - 2):
		(a[1], a[~i]) = (a[~i], a[1])
		print(*a)
	(a[0], a[-1]) = (a[-1], a[0])
	print(*a)


Tests = int(input())
for _ in range(Tests):
	m = int(input())
	n = [i + 1 for i in range(m)]
	print(m)
	print(' '.join(map(str, n)))
	for i in range(m - 1):
		(n[i], n[i + 1]) = (n[i + 1], n[i])
		print(' '.join(map(str, n)))


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


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


t = int(input())
for i in range(t):
	n = int(input())
	l = list(range(1, n + 1))
	print(n)
	print(' '.join(map(str, l)))
	k = 0
	for j in range(n - 1):
		temp = l[k]
		l[k] = l[k + 1]
		l[k + 1] = temp
		print(' '.join(map(str, l)))
		k = k + 1


t = int(input().strip())

def dontknowwhattowrite(n):
	a = [n]
	if n == 1:
		return a
	for i in range(n - 1):
		a.append(i + 1)
	return a
for _ in range(t):
	n = int(input().strip())
	print(n)
	a = [x + 1 for x in range(n)]
	print(str(a).replace(',', '').replace('[', '').replace(']', ''))
	if n == 1:
		continue
	elif n == 2:
		print('2 1')
	if n >= 3:
		for i in range(2, n + 1):
			t = dontknowwhattowrite(i) + a[i:n]
			print(str(t).replace(',', '').replace('[', '').replace(']', ''))


for _ in range(int(input())):
	n = int(input())
	array = [i + 1 for i in range(n)]
	print(n)
	print(' '.join(map(str, array)))
	idx = 0
	while idx < len(array) - 1:
		(array[idx], array[idx + 1]) = (array[idx + 1], array[idx])
		print(' '.join(map(str, array)))
		idx += 1


for _ in range(int(input())):
	L = [x for x in range(1, int(input()) + 1)]
	n = len(L)
	print(n)
	print(' '.join(list(map(str, L))))
	for j in range(1, n):
		(L[0], L[j]) = (L[j], L[0])
		print(' '.join(list(map(str, L))))


def chain(n):
	print(n)
	ans = [i for i in range(1, n + 1)]
	curr = 0
	print(' '.join(list(map(str, ans))))
	while curr < n - 1:
		(ans[curr], ans[n - 1]) = (ans[n - 1], ans[curr])
		print(' '.join(list(map(str, ans))))
		curr += 1
t = int(input())
for _ in range(t):
	n = int(input())
	chain(n)


t = int(input())
for case in range(t):
	n = int(input())
	perms = list()
	first_permutation = [int(i) for i in range(1, n + 1)]
	perms.append(first_permutation)
	current_permutation = first_permutation.copy()
	for i in range(n - 1):
		aux = current_permutation[i]
		current_permutation[i] = current_permutation[n - 1]
		current_permutation[n - 1] = aux
		perms.append(current_permutation.copy())
	print(len(perms))
	for i in range(len(perms)):
		print(' '.join(map(str, perms[i])))


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


import sys
t = int(sys.stdin.readline())
while t:
	t -= 1
	n = int(sys.stdin.readline())
	a = list(range(1, n + 1))
	print(n)
	print(' '.join(map(str, a)))
	for i in range(n - 1):
		if i == 0:
			(a[0], a[-1]) = (a[-1], a[0])
		else:
			(a[n - i - 1], a[n - i]) = (a[n - i], a[n - i - 1])
		print(' '.join(map(str, a)))


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


def ans(n):
	r = []
	a = []
	for i in range(1, n + 1):
		a.append(i)
	l = a[0:n]
	r.append(l)
	for i in range(n - 1, 0, -1):
		k = a[i]
		a[i] = a[i - 1]
		a[i - 1] = k
		l = a[0:n]
		r.append(l)
	return r
T = int(input())
l = []
for _ in range(T):
	n = int(input())
	c = ans(n)
	l.append(c)
for i in range(T):
	print(len(l[i]))
	for j in range(len(l[i])):
		print(' '.join(map(str, l[i][j])))


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


test_cases = int(input())
for i in range(test_cases):
	l = int(input())
	print(l)
	chain = list(range(1, l + 1))
	print(' '.join([str(i) for i in chain]))
	for i in range(l - 1):
		(chain[l - (i + 1)], chain[l - (i + 2)]) = (chain[l - (i + 2)], chain[l - (i + 1)])
		print(' '.join([str(i) for i in chain]))


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


numcase = int(input())
re = []

def send(lis):
	b = [str(j) for j in lis]
	return ' '.join(b)
for i in range(numcase):
	lenlis = int(input())
	re.append(lenlis)
	lis1 = []
	for i in range(1, lenlis + 1):
		lis1.append(i)
	re.append(send(lis1))
	for i in range(lenlis - 1):
		a = lenlis - 1 - i
		b = lenlis - 2 - i
		(lis1[b], lis1[a]) = (lis1[a], lis1[b])
		re.append(send(lis1))
for term in re:
	print(term)


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


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


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


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


def swap(a, i, j):
	(a[i], a[j]) = (a[j], a[i])
	return a

def repr(a):
	print(' '.join([str(i) for i in a]))

def permu(n):
	print(n)
	arr = [i for i in range(1, n + 1)]
	repr(arr)
	for i in range(2, n + 1)[::-1]:
		arr = swap(arr, i - 1, i - 2)
		repr(arr)
k = int(input())
for _ in range(k):
	permu(int(input()))


def solve():
	n = int(input())
	a = list(range(1, n + 1))
	print(n)
	print(' '.join((str(i) for i in a)))
	for i in range(n - 1):
		(a[i], a[i + 1]) = (a[i + 1], a[i])
		print(' '.join((str(j) for j in a)))
for _ in range(int(input())):
	ans = solve()


def swap(arr, i1, i2):
	(arr[i1], arr[i2]) = (arr[i2], arr[i1])
	return arr
for i in range(int(input())):
	n = int(input())
	arr = [k for k in range(1, n + 1)]
	print(n)
	for i in range(n - 1):
		print(' '.join([str(num) for num in arr]))
		arr = swap(arr, i, n - 1)
	print(' '.join([str(num) for num in arr]))


def solve():
	n = int(input())
	tc = list()
	for i in range(n):
		tc.append(int(input()))
	for test in tc:
		initial = [_ for _ in range(1, test + 1)]
		last = [initial[-1]] + initial
		last.pop()
		print(test)
		print(arrToStr(initial))
		l = 0
		r = test - 1
		c = True
		for i in range(test - 1):
			t = initial[l]
			initial[l] = initial[r]
			initial[r] = t
			if c:
				l += 1
				c = False
			else:
				r -= 1
				c = True
			print(arrToStr(initial))

def arrToStr(arr):
	s = ''
	for val in arr:
		s += f'{val} '
	s = s[0:len(s) - 1]
	return s
solve()


t = int(input())
sol = []
for _ in range(t):
	n = int(input())
	s = []
	nums = [i for i in range(n)]
	s.append(nums)
	for i in range(1, n):
		nums = nums[:]
		tmp = nums[i]
		nums[i] = nums[i - 1]
		nums[i - 1] = tmp
		s.append(nums)
	sol.append(s)
for s in sol:
	print(len(s))
	for si in s:
		print(' '.join([str(i + 1) for i in si]))


def main():
	output = 0
	N = int(input())
	l = [i + 1 for i in range(N)]
	x = 0
	print(N)
	while x < N - 1:
		print(' '.join((str(z) for z in l)))
		if x % 2 == 0:
			t = l[0]
			l[0] = l[x + 1]
			l[x + 1] = t
		else:
			t = l[1]
			l[1] = l[x + 1]
			l[x + 1] = t
		x += 1
	print(' '.join((str(z) for z in l)))
	return output
num_of_cases = [int(i) for i in input().split()][0]
for p in range(num_of_cases):
	output = main()


def permutation_chain(n):
	k = [i for i in range(1, n + 1)]
	print(' '.join((str(i) for i in k)))
	for i in range(n - 1):
		(k[i], k[i + 1]) = (k[i + 1], k[i])
		print(' '.join((str(i) for i in k)))
num_cases = int(input())
for i in range(num_cases):
	case_value = int(input())
	print(case_value)
	permutation_chain(case_value)


import math
t = int(input())

def solve():
	n = int(input())
	arr = [i for i in range(1, n + 1)]
	brr = [i for i in range(1, n + 1)]
	print(n)
	print(' '.join((str(ele) for ele in brr)))
	for i in range(1, n):
		curr = brr.pop(i)
		brr = [curr] + brr
		print(' '.join((str(ele) for ele in brr)))
		brr = arr.copy()
while t:
	solve()
	t -= 1


tests = int(input())
nums = []
save = []
for i in range(tests):
	n = int(input())
	save.append(n)
	p = list(range(1, n + 1))
	nums.append(p)
for j in range(tests):
	print(max(nums[j]))
	print(' '.join((str(e) for e in nums[j])))
	lt = nums[j]
	for m in range(len(lt) - 1, 0, -1):
		templist = lt
		(templist[0], templist[m]) = (templist[m], templist[0])
		print(' '.join((str(x) for x in templist)))


def fixedness(a):
	f = 0
	for (k, v) in enumerate(a):
		if k + 1 == v:
			f += 1
	return f

def permute(n):
	perm = {}
	SIZE = n
	n = [v + 1 for v in range(n)]
	a = n.copy()
	f = fixedness(a)
	perm[f] = a.copy()
	for i in range(SIZE - 1, 1, -1):
		(a[i], a[i - 1]) = (a[i - 1], a[i])
		f = fixedness(a)
		if perm.get(f) == None:
			perm[f] = a.copy()
	(a[0], a[1]) = (a[1], a[0])
	f = fixedness(a)
	perm[f] = a.copy()
	perm = dict(sorted(perm.items(), reverse=True))
	return perm

def main():
	t = input()
	t = int(t)
	for i in range(t):
		n = input()
		n = int(n)
		p = permute(n)
		print(n)
		for k in p:
			v = ' '.join([str(d) for d in p[k]])
			print(v)
main()


def findF(perm):
	f = 0
	for (i, elem) in enumerate(perm):
		if i + 1 == elem:
			f += 1
	return f

def solveFor(x):
	a = [i + 1 for i in range(x)]
	iterations = []
	f = x
	iterations.append(' '.join([str(i) for i in a.copy()]))
	for (i, _) in enumerate(a):
		(a[0], a[i]) = (a[i], a[0])
		_f = findF(a)
		if _f < f:
			f = _f
			iterations.append(' '.join([str(i) for i in a.copy()]))
	return '\n'.join(iterations)
for _ in range(int(input())):
	x = int(input())
	print(x)
	print(solveFor(x))


from sys import stdin
rd = stdin.readline
for _ in range(int(rd())):
	n = int(rd())
	print(n)
	l = [i for i in range(1, n + 1)]
	print(' '.join(map(str, l)))
	while l[0] != n:
		x = l.index(n)
		(l[x], l[x - 1]) = (l[x - 1], l[x])
		print(' '.join(map(str, l)))


def listToString(s):
	str1 = ''
	for ele in s:
		str1 += str(ele) + ' '
	print(str1)

def permutations(n):
	list2 = []
	list = [i + 1 for i in range(n)]
	for i in range(n):
		listToString([list[i]] + list[:i] + list[i + 1:])
t = int(input())
for i in range(t):
	n = int(input())
	print(n)
	permutations(n)


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

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

def printlis(lis):
	ans = ''
	for i in lis:
		ans += str(i) + ' '
	print(ans)

def main():
	t = int(input())
	for i in range(t):
		n = int(input())
		lis = list(range(1, n + 1))
		print(n)
		printlis(lis)
		a = lis[0]
		lis[0] = lis[n - 1]
		lis[n - 1] = a
		printlis(lis)
		for i in range(n - 2):
			a = lis[n - i - 1]
			lis[n - i - 1] = lis[n - i - 2]
			lis[n - i - 2] = a
			printlis(lis)
main()


def LtoS(L):
	s = ''
	for i in range(len(L)):
		s += str(L[i])
		s += ' '
	return s

def iffixed(e, L):
	if L.index(e) == e - 1:
		return True
	else:
		return False
t = int(input())
for i in range(t):
	n = int(input())
	L = []
	for j in range(n):
		L.append(j + 1)
	print(n)
	print(LtoS(L))
	for k in range(len(L)):
		a = 0
		b = 0
		if k == 0:
			pass
		elif k == 1:
			(L[0], L[1]) = (L[1], L[0])
			print(LtoS(L))
		elif iffixed(L[k], L):
			a = L[k]
			b = L[0]
			(L[L.index(a)], L[L.index(b)]) = (L[L.index(b)], L[L.index(a)])
			print(LtoS(L))
		else:
			pass


t = int(input())
que = []
for _ in range(t):
	que.append(int(input()))
for i in que:
	print(i)
	ans1 = list(range(i + 1))[1:]
	s = ''
	for _ in ans1:
		s = s + str(_) + ' '
	s = s.rstrip()
	print(s)
	x = len(ans1) - 1
	y = len(ans1) - 2
	for _ in range(i - 1):
		(ans1[x], ans1[y]) = (ans1[y], ans1[x])
		x -= 1
		y -= 1
		s = ''
		for _ in ans1:
			s = s + str(_) + ' '
		s = s.rstrip()
		print(s)


t = int(input())
for _ in range(t):
	a = []
	f = []
	k = int(input())
	print(k)
	a.append(list(range(1, k + 1)))
	f.append(k)
	for i in range(k):
		print(' '.join((str(x) for x in a[i])))
		ai = a[i]
		fi = f[i]
		if f[i] == k:
			(ai[i], ai[i + 1]) = (ai[i + 1], ai[i])
			fi -= 2
		else:
			(swp1, swp2) = (-1, -1)
			for (j, e) in enumerate(ai):
				if e != j + 1 and swp1 == -1:
					swp1 = j
				elif e == j + 1 and swp2 == -1:
					swp2 = j
				elif swp1 != -1 and swp2 != -1:
					break
			(ai[swp1], ai[swp2]) = (ai[swp2], ai[swp1])
			fi -= 1
		a.append(ai)
		f.append(fi)


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


for _ in range(int(input())):
	n = int(input())
	a1 = [ele for ele in range(1, n + 1)]
	print(n)
	s = ''
	for ele in a1:
		s += str(ele) + ' '
	print(s)
	for i in range(n - 1, 0, -1):
		a = a1[i]
		a1[i] = a1[i - 1]
		a1[i - 1] = a
		s = ''
		for e in a1:
			s += str(e) + ' '
		print(s)


import math
n = int(input())
for i in range(n):
	x = int(input())
	print(x)
	z = []
	for j in range(x):
		z.append(j + 1)
	n = ''
	for l in range(x):
		n = n + str(z[l]) + ' '
	print(n)
	for j in range(x - 1):
		f = z[j]
		z[j] = z[j + 1]
		z[j + 1] = f
		m = ''
		for l in range(x):
			m = m + str(z[l]) + ' '
		print(m)


n = int(input())
for _ in range(n):
	data = int(input())
	perms = []
	aux = []
	for i in range(data):
		aux.append(i + 1)
	perms.append(aux)
	for i in range(data - 1):
		aux = perms[i].copy()
		(aux[i], aux[-1]) = (aux[-1], aux[i])
		perms.append(aux)
	print(data)
	for i in perms:
		st = ''
		for j in i:
			st += str(j)
			st += ' '
		print(st)


def swap(arr, i, j):
	aux = arr[i]
	arr[i] = arr[j]
	arr[j] = aux
t = int(input())
for _ in range(t):
	n = int(input())
	print(n)
	first_permutation = [str(k) for k in range(1, n + 1)]
	print(*first_permutation)
	swap(first_permutation, 0, n - 1)
	print(*first_permutation)
	i = n - 2
	while i > 0:
		swap(first_permutation, i + 1, i)
		print(*first_permutation)
		i -= 1


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


n = int(input())
for i in range(n):
	s = int(input())
	print(s)
	l = list(range(1, s + 1))
	print(*l)
	for j in range(s - 1):
		(l[j], l[s - 1]) = (l[s - 1], l[j])
		print(*l)


for _ in range(int(input())):
	n = int(input())
	k = []
	for i in range(n):
		k.append(i + 1)
	i = 1
	print(n)
	print(*k)
	while i < len(k):
		(k[0], k[i]) = (k[i], k[0])
		i += 1
		print(*k)


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


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


from collections import deque
from math import gcd, factorial, sqrt, pi
from functools import lru_cache
from itertools import permutations
I = lambda : input()
IN = lambda : int(input())
M = lambda : map(int, input().strip().split())
L = lambda : list(map(int, input().strip().split()))
LCHR = lambda : [i for i in input()]
LW = lambda : [i for i in input().split()]
LCM = lambda a, b: a * b // gcd(a, b)
for _ in range(IN()):
	n = IN()
	l = [i for i in range(1, n + 1)]
	print(n)
	print(*l)
	for i in range(1, n):
		(l[i], l[i - 1]) = (l[i - 1], l[i])
		print(*l)


def inp_a():
	return [int(x) for x in input().split()]

def inp_s(k):
	arr = []
	for i in range(k):
		arr.append(input())
	return arr

def help(n):
	count = 1
	ans = []
	p = []
	for i in range(1, n + 1):
		p.append(i)
	ans.append(list(p))
	(p[0], p[-1]) = (p[-1], p[0])
	ans.append(list(p))
	count = 2
	for i in range(n - 2):
		(p[i], p[i + 1]) = (p[i + 1], p[i])
		ans.append(list(p))
		count += 1
	return (count, ans)
for _ in range(int(input())):
	n = int(input())
	(c, a) = help(n)
	print(c)
	for i in a:
		print(*i)


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


for i in range(int(input())):
	length = int(input())
	list1 = []
	for j in range(1, length + 1):
		list1.append(j)
	if length == 1:
		print(length)
		print(*list1)
	else:
		print(length)
		print(*list1)
		(list1[0], list1[1]) = (list1[1], list1[0])
		position = 2
		print(*list1)
		while position != length:
			(list1[position - 1], list1[position]) = (list1[position], list1[position - 1])
			position += 1
			print(*list1)


for i in range(int(input())):
	n = int(input())
	print(n)
	lst = []
	flag = n - 1
	temp = 0
	for j in range(1, n + 1):
		lst.append(j)
	print(*lst)
	for j in range(n - 1):
		(lst[flag], lst[flag - 1]) = (lst[flag - 1], lst[flag])
		flag -= 1
		print(*lst)


import sys
from os import path
import os
from collections import defaultdict
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
for _ in range(int(input())):
	n = int(input())
	a = [i for i in range(1, n + 1)]
	print(n)
	m = n
	i = 0
	while m:
		print(*a)
		(a[i], a[i + 1]) = (a[i + 1], a[i])
		i -= 1
		m -= 1