Let's call a permutation $p$ of length $n$ anti-Fibonacci if the condition $p_{i-2} + p_{i-1} \ne p_i$ holds for all $i$ ($3 \le i \le n$). Recall that the permutation is the array of length $n$ which contains each integer from $1$ to $n$ exactly once.

Your task is for a given number $n$ print $n$ distinct anti-Fibonacci permutations of length $n$.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 48$) — the number of test cases.

The single line of each test case contains a single integer $n$ ($3 \le n \le 50$).


-----Output-----

For each test case, print $n$ lines. Each line should contain an anti-Fibonacci permutation of length $n$. In each test case, you cannot print any permutation more than once.

If there are multiple answers, print any of them. It can be shown that it is always possible to find $n$ different anti-Fibonacci permutations of size $n$ under the constraints of the problem.


-----Examples-----

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


-----Note-----

None

Source: codeforces | Difficulty: EASY
Tags: Complete search

Implementation

Constructive algorithms


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


t = int(input())
result = []
for i in range(t):
	n = int(input())
	if n == 3:
		result.append('3 2 1')
		result.append('3 1 2')
		result.append('1 3 2')
	else:
		array = [str(j) for j in range(n, 0, -1)]
		result.append(' '.join(array))
		for j in range(n - 1):
			array.insert(0, array[n - 1])
			del array[n]
			result.append(' '.join(array))
for i in result:
	print(i)


t = int(input())

def q(n):
	if n == 3:
		return '3 2 1\n3 1 2\n1 3 2'
for i in range(t):
	n = int(input())
	l = [str(i) for i in range(1, n + 1)]
	(l[1], l[2]) = ('3', '2')
	if n != 3:
		print(' '.join(l))
		for k in range(n - 1):
			val = l[0]
			l.remove(val)
			l.append(val)
			print(' '.join(l))
	else:
		print(q(3))


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


nbTest = int(input())

def swap(orig, i, j):
	new = orig.copy()
	tmp = new[i]
	new[i] = new[j]
	new[j] = tmp
	return new
for testN in range(nbTest):
	n = int(input())
	original = []
	for i in range(n, -1, -1):
		original.append(str(i))
	original.remove('0')
	print(' '.join(original))
	for i in range(n - 1):
		new = swap(original, i, i + 1)
		print(' '.join(new))


def solve():
	n = int(input())
	if n == 3:
		print('3 2 1')
		print('1 3 2')
		print('3 1 2')
	else:
		ans = [str(x) for x in list(range(n, 0, -1))]
		for i in range(n):
			print(' '.join(ans))
			ans = [ans[-1]] + ans[:-1]
for tc in range(int(input())):
	solve()


global cur
cur = 0

def solve(a):
	n = a
	out = []
	for k in range(1, n + 1):
		s = [i for i in range(n, k, -1)] + [1] + [i + 1 for i in range(k - 1, 0, -1)]
		out.append(' '.join(map(str, s)))
	return '\n'.join(out)
out = []
t = int(input())
for case in range(t):
	s = int(input())
	out.append(str(solve(s)))
print('\n'.join(out))


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


def find(N):
	result = [str(x) for x in range(1, N + 1)]
	result.reverse()
	s0 = ' '.join(result)
	print(s0)
	result.reverse()
	if N > 1:
		one = result.pop(0)
		result.append(one)
		s1 = ' '.join(result)
		print(s1)
		two = result.pop(0)
		result.append(two)
		s2 = ' '.join(result)
		print(s2)
		three = result.pop(0)
		for i in range(0, n - 3):
			first = result.pop(0)
			result.append(first)
			result.append(three)
			s = ' '.join(result)
			print(s)
			result.pop()
	return
num = int(input())
for i in range(num):
	n = int(input())
	find(n)


t = int(input())
for i in range(t):
	n = int(input())
	arr1 = [str(i) for i in range(1, n + 1)]
	arr = sorted(arr1, reverse=True)
	k = 0
	for j in range(n):
		(arr[k], arr[0]) = (arr[0], arr[k])
		print(' '.join(arr))
		k += 1


def func(n):
	res = ''
	arr = [str(i) for i in range(n, 0, -1)]
	for i in range(n):
		res += ' '.join(arr)
		if i < n - 1:
			res += '\n'
		(arr[n - i - 1], arr[n - i - 2]) = (arr[n - i - 2], arr[n - i - 1])
	return res
t = int(input())
for _ in range(t):
	n = int(input())
	print(func(n))


n = int(input())
a = [[['3', '2', '1'], ['3', '1', '2'], ['1', '3', '2']]] * 50
for i in range(3, 50):
	a[i] = a[i - 1] + [a[i - 1][0]]
	for j in range(i + 1):
		a[i][j] = [str(i + 1)] + a[i][j]
	a[i][j] = [a[i][j][1]] + [a[i][j][0]] + a[i][j][2:]
for i in range(n):
	b = int(input())
	for j in a[b - 1]:
		print(' '.join(j))


test = int(input())
for t in range(test):
	n = int(input())
	original = [str(i) for i in range(1, n + 1)]
	original.reverse()
	x = ' '.join(original)
	print(x)
	i = 0
	while i < n - 1:
		arr = original.copy()
		(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
		x = ' '.join(arr)
		print(x)
		i += 1


t = int(input())
for i in range(t):
	tamanho = int(input())
	if tamanho > 3:
		a = list(range(1, tamanho + 1))
		a = a[::-1]
		print(' '.join(map(str, a)))
		risk = tamanho // 2
		for j in range(1, tamanho):
			if j == risk + 2:
				(a[j - risk], a[j - risk - 1]) = (a[j - risk - 1], a[j - risk])
				print(' '.join(map(str, a)))
				(a[j - risk - 1], a[j - risk]) = (a[j - risk], a[j - risk - 1])
			else:
				(a[0], a[j]) = (a[j], a[0])
				print(' '.join(map(str, a)))
				(a[0], a[j]) = (a[j], a[0])
	else:
		print(3, 2, 1)
		print(2, 3, 1)
		print(1, 3, 2)


def shift(a: list):
	end = a[0]
	a.pop(0)
	a.append(end)

def buildNAntiFibo(n):
	if n == 3:
		return [[3, 2, 1], [1, 3, 2], [3, 1, 2]]
	ret = []
	count = n - 1
	a = [n - x for x in range(n)]
	ret.append(a.copy())
	while count > 0:
		shift(a)
		count -= 1
		ret.append(a.copy())
	return ret
t = int(input())
for i in range(t):
	n = int(input())
	perms = buildNAntiFibo(n)
	for perm in perms:
		print(' '.join(map(str, perm)))


n = int(input())
for i in range(n):
	x = int(input())
	l = [str(i) for i in range(1, x + 1)]
	for j in range(x):
		if x == 3 and l[0] == '3':
			print('2 3 1')
		else:
			print(' '.join(l[::-1]))
		l.pop(0)
		l.append(str(int(l[0]) - 1))


for i in range(int(input())):
	n = int(input())
	a = list(range(2, n + 1))
	a.sort(reverse=True)
	k = ' 1 '
	a = list(map(str, a))
	for i in range(n):
		print(' '.join(a[:i]) + k + ' '.join(a[i:]))


num = int(input())
for i in range(num):
	nums = int(input())
	lst = temp = [str(i) for i in range(1, nums + 1)][::-1]
	for j in range(nums):
		(lst[0], lst[j]) = (lst[j], lst[0])
		print(' '.join(lst))
		lst = temp


t = int(input())
while t > 0:
	n = int(input())
	S = []
	for q in range(1, n + 1):
		S.append(str(n + 1 - q) + ' ')
	S *= 2
	if n > 3:
		for i in range(0, n):
			print(''.join(S[i:i + n]))
	else:
		print(1, 3, 2)
		print(3, 1, 2)
		print(3, 2, 1)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	l = []
	for i in range(1, n + 1):
		l.append(i)
	l = l[::-1]
	res = [l.copy()]
	for i in range(2, n):
		(l[0], l[i]) = (l[i], l[0])
		res.append(l.copy())
		(l[0], l[i]) = (l[i], l[0])
		(l[1], l[i]) = (l[i], l[1])
		res.append(l.copy())
		(l[1], l[i]) = (l[i], l[1])
	if n % 2 == 1 and n != 3:
		res.append(l[::-1])
	if n == 3:
		res = [[3, 2, 1], [2, 3, 1], [1, 3, 2]]
	for x in res[:n]:
		k = [str(a) for a in x]
		print(' '.join(k))


import sys

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

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

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

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

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

def get_print_int(x):
	sys.stdout.write(str(x) + '\n')

def get_print(x):
	sys.stdout.write(x + '\n')

def get_print_int_same(x):
	sys.stdout.write(str(x) + ' ')

def get_print_same(x):
	sys.stdout.write(x + ' ')

def solve():
	dp = []
	dp.append([[2, 3, 1], [3, 1, 2], [3, 2, 1]])
	for i in range(4, 51, 1):
		ans = [[]]
		prev = dp[i - 3 - 1]
		for j in prev:
			cj = j[:]
			cj.insert(0, i)
			ans.append(cj)
		last = ans[-1][:]
		(last[0], last[1]) = (last[1], last[0])
		ans[0] = last
		dp.append(ans)
	for _ in range(get_int()):
		n = get_int()
		ans = dp[n - 3]
		for i in ans:
			get_print(' '.join(map(str, i)))
solve()


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


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	if n == 3:
		print('3 2 1')
		print('2 3 1')
		print('1 3 2')
	else:
		for i in range(n):
			lst = list(range(n - 1, 0, -1))
			if n % 2 and i + 1 == n // 2 + 2:
				lst = list(range(1, n + 1))
				(lst[-1], lst[0]) = (lst[0], lst[-1])
			else:
				lst.insert(i, n)
			print(' '.join(map(str, lst)))


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


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


from collections import deque
for _ in range(int(input())):
	n = int(input())
	if n == 3:
		print('3 2 1')
		print('3 1 2')
		print('1 3 2')
	else:
		ns = deque(map(str, range(n, 0, -1)))
		for _ in range(n):
			print(' '.join(ns))
			ns.rotate()


T = int(input())

def print_seq(l):
	print(' '.join([str(i) for i in l]))
for _ in range(T):
	n = int(input())
	if n == 3:
		print_seq([3, 2, 1])
		print_seq([1, 3, 2])
		print_seq([3, 1, 2])
	else:
		print_seq(list(range(n, 0, -1)))
		base_seq = list(range(2, n + 1))
		for i in range(n - 1):
			print_seq(base_seq[i:] + base_seq[:i] + [1])


for _ in range(int(input())):
	n = int(input())
	l = ['1', '3', '2', '4']
	while len(l) > n:
		l.pop()
	for x in range(5, n + 1):
		l.append(str(x))
	if n == 3:
		print('1 3 2')
		print('3 2 1')
		print('3 1 2')
	else:
		for x in range(n):
			print(' '.join(l[x:]) + ' ' + ' '.join(l[:x]))


n = int(input())
for i in range(n):
	num = int(input())
	perm = []
	for i in range(num):
		perm.append(num - i)
	if num == 3:
		print('1 3 2')
		print('2 3 1')
		print('3 2 1')
	else:
		for j in range(num):
			temp = perm[0]
			perm.pop(0)
			perm.append(temp)
			print(' '.join(list(map(str, perm))))


import sys
import math
strInp = lambda : input().strip().split()
intInp = lambda : list(map(int, strInp()))

def gen(init, n):
	newInit = []
	for i in range(n - 1):
		newInit.append([n] + init[i])
	last = list.copy(newInit[n - 2])
	tmp = last[0]
	last[0] = last[1]
	last[1] = tmp
	newInit.append(last)
	return newInit
for t in range(int(input())):
	n = int(input())
	init = [[3, 2, 1], [3, 1, 2], [1, 3, 2]]
	for i in range(4, n + 1):
		init = gen(init, i)
	for i in init:
		print(' '.join((str(e) for e in i)))


num_tests = int(input())
inputs = []
outputs = []
for _ in range(num_tests):
	inputs.append(int(input()))
for n in inputs:
	descending = list(range(n - 1, 0, -1))
	largest_elem = n
	for i in range(n):
		output = descending.copy()
		output.insert(i, largest_elem)
		if n % 2 == 1 and i >= 2:
			if descending[i - 2] + descending[i - 1] == largest_elem:
				tmp1 = output[i - 1]
				tmp2 = output[i - 2]
				output[i - 1] = largest_elem
				output[i - 2] = tmp1
				output[i] = tmp2
		outputs.append(' '.join((str(num) for num in output)))
for output in outputs:
	print(output)


for i in range(int(input())):
	n = int(input())
	a = []
	if n == 3:
		print('2 3 1')
		print('3 1 2')
		print('3 2 1')
	else:
		for i in range(n):
			a.append(i + 1)
		a.reverse()
		for i in range(n):
			a.append(a[0])
			a.remove(a[0])
			a = list(map(str, a))
			print(' '.join(a))


from enum import Enum, auto
import copy
import sys
input = sys.stdin.readline

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


def reverse(l, i, j):
	while i < j:
		temp = l[i]
		l[i] = l[j]
		l[j] = temp
		i += 1
		j -= 1

def rotate(l):
	reverse(l, 0, len(l) - 2)
	reverse(l, 0, len(l) - 1)

def display(l):
	print(' '.join(map(str, l)))
t = int(input())
for i in range(t):
	n = int(input())
	l = list(range(n, 0, -1))
	for i in range(n):
		if n == 3 and i == 2:
			temp = l[0]
			l[0] = l[2]
			l[2] = temp
			display(l)
		else:
			display(l)
			rotate(l)


import itertools
from sys import stdin
n = int(stdin.readline())
for _ in range(n):
	x = int(stdin.readline())
	d = list(range(3, x + 1)) + [1]
	for i in range(x):
		d.insert(i, 2)
		print(str.join(' ', map(str, d)))
		d.pop(i)


def readLineToInts():
	return [int(item) for item in input().split()]
tn = readLineToInts()[0]
for ti in range(tn):
	n = readLineToInts()[0]
	for i in range(n):
		curans = ([j + 1 for j in range(n) if j != i] + [i + 1])[::-1]
		print(' '.join([str(x) for x in curans]))


def anti_fib(t, lnt):
	for i in range(lnt - 2):
		if t[i] + t[i + 1] == t[i + 2]:
			return False
	return True

def generate_perm(x):
	perm = [[], [], [(1, 2), (2, 1)]]
	n = 3
	while n <= 4:
		nxt = []
		for t in perm[-1]:
			for i in range(n):
				nxt.append(t[:i] + (n,) + t[i:])
		perm.append(nxt)
		n += 1
	while n <= x:
		nxt = []
		for t in perm[-1]:
			for i in range(n):
				tup = t[:i] + (n,) + t[i:]
				if anti_fib(tup, n):
					nxt.append(tup)
			if len(nxt) > x:
				break
		perm.append(nxt)
		n += 1
	perm[3] = [(1, 3, 2), (3, 1, 2), (2, 3, 1), (3, 2, 1)]
	nw = []
	for tup in perm[4]:
		if anti_fib(tup, 4):
			nw.append(tup)
	perm[4] = nw
	return tuple(perm)
per = generate_perm(50)
af = [[], [], []]
for i in range(3, 51):
	nxt = []
	for j in range(i):
		s = ''
		for k in per[i][j]:
			s += str(k) + ' '
		nxt.append(s.rstrip())
	af.append(nxt)
t = int(input())
while t > 0:
	for s in af[int(input())]:
		print(s)
	t -= 1


from itertools import permutations

def notFib(arr):
	for i in range(len(arr) - 2):
		if arr[i] + arr[i + 1] == arr[i + 2]:
			return False
	return True
t = int(input())
for i in range(t):
	n = int(input())
	a = [int(x) + 1 for x in range(n)]
	a.reverse()
	perm = permutations(a, n)
	c = 0
	for i in perm:
		if notFib(i):
			print(' '.join([str(x) for x in i]))
			c += 1
			if c == n:
				break


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


import copy
for t in range(int(input())):
	n = int(input())
	if n == 3:
		print('3 2 1')
		print('2 3 1')
		print('3 1 2')
		continue
	elif n == 5:
		print('5 4 3 2 1')
		print('5 4 3 1 2')
		print('5 3 4 1 2')
		print('5 3 4 2 1')
		print('4 5 3 2 1')
		continue
	res = list()
	for i in range(min(6, n // 2)):
		ln = len(res)
		if ln > 0:
			j = 0
			while j < ln:
				tmp = copy.deepcopy(res[j])
				res.append(tmp)
				j += 1
			for l in range(ln):
				res[l].extend([2 * i + 1, 2 * i + 2])
			for l in range(ln, 2 * ln):
				res[l].extend([2 * i + 2, 2 * i + 1])
		else:
			res.append([1 << i, (1 << i) + 1])
			res.append([(1 << i) + 1, 1 << i])
	cnt = 0
	for each in res:
		if len(each) < n:
			each.extend([k for k in range(len(each) + 1, n + 1)])
		if cnt < n:
			print(' '.join(list(map(str, [ele for ele in reversed(each)]))))
			cnt += 1
		else:
			break


import math
import sys
import itertools
import fractions
import random
wtf = sys.stdin.read()
wtf = wtf.strip().split('\n')
for t in wtf[1:]:
	n = int(t)
	fibs = []
	for i in range(n, 0, -1):
		fibs.append(i)
	for i in range(n):
		print(' '.join(map(str, fibs)))
		if i + 1 == n:
			break
		if i > 0 and i < n - 1:
			if fibs[i - 1] + fibs[i + 1] == fibs[i]:
				(fibs[i - 1], fibs[i + 1]) = (fibs[i + 1], fibs[i - 1])
				continue
		(fibs[i], fibs[i + 1]) = (fibs[i + 1], fibs[i])


for _ in range(int(input())):
	a = int(input())
	lst = [i + 1 for i in range(a)]
	res = []
	for i in lst:
		pl = str(i)
		for c in lst[:i - 1:-1]:
			pl += ' ' + str(c)
		if i != 1:
			for c in lst[i - 2::-1]:
				pl += ' ' + str(c)
		res.append(pl)
	print(*res, sep='\n')


tc = int(input())
for i in range(tc):
	x = int(input())
	if x == 3:
		print('3 2 1')
		print('1 3 2')
		print('3 1 2')
	else:
		list1 = []
		for j in range(x, 0, -1):
			list1.append(j)
		for i in range(x, 0, -1):
			list2 = list1[i:] + list1[:i]
			str1 = ''
			for i in list2:
				str1 += str(i) + ' '
			print(str1)


from collections import OrderedDict
for _ in range(int(input())):
	n = int(input())
	x = [i for i in range(1, n + 1)]
	y = x[::-1]
	for i in range(1, n):
		new = [e for e in range(n, 0, -1) if e != y[-i]]
		q = [y[0], y[-i]] + new
		ans = list(OrderedDict.fromkeys(q))
		print(' '.join((str(i) for i in ans)))
	(y[0], y[1]) = (y[1], y[0])
	print(' '.join((str(i) for i in y)))


t = int(input())
for _ in range(0, t):
	n = int(input())
	list1 = []
	s = ''
	for i in range(n, 0, -1):
		list1.append(i)
		s += str(i) + ' '
	print(s.strip())
	i = 1
	for i in range(1, n):
		temp = list1[i]
		list1[i] = list1[0]
		list1[0] = temp
		s = ''
		if i >= 2 and list1[i - 1] + list1[i - 2] == list1[i]:
			temp = list1[i - 1]
			list1[i - 1] = list1[i]
			list1[i] = temp
			j = 0
			for j in range(0, n):
				s += str(list1[j]) + ' '
			print(s.strip())
			temp = list1[i - 1]
			list1[i - 1] = list1[i]
			list1[i] = temp
		else:
			j = 0
			for j in range(0, n):
				s += str(list1[j]) + ' '
			print(s.strip())
		temp = list1[i]
		list1[i] = list1[0]
		list1[0] = temp


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


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


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


for ii in range(int(input())):
	n = int(input())
	if n == 5:
		l = [jj for jj in range(n, 0, -1)]
		for jj in range(n - 1):
			print(*l[jj:] + l[:jj])
		print(*l[:-2], 1, 2)
	else:
		l = [jj for jj in range(n, 1, -1)]
		for jj in range(n - 1):
			print(*l[jj:] + l[:jj], 1)
		print(*l[:-1], 1, 2)


import itertools

def case1(n):
	count = 0
	out = []
	s = [i for i in range(1, n + 1)]
	for i in itertools.permutations(s, r=n):
		if count == n:
			break
		i = list(i)
		flag = True
		for x in range(2, n):
			if i[x] == i[x - 1] + i[x - 2]:
				flag = False
				break
		if flag:
			count += 1
			out += [i]
	return out

def case2(n):
	s = [i for i in range(1, n - 4)]
	(s[2], s[3]) = (s[3], s[2])
	d = [i for i in range(n - 4, n + 1)]
	count = 0
	out = []
	for i in itertools.permutations(d, r=5):
		if count == n:
			break
		out += [s + list(i)]
		count += 1
	return out
for _ in range(int(input())):
	n = int(input())
	if n <= 9:
		for i in case1(n):
			print(*i)
	if n >= 10:
		for i in case2(n):
			print(*i)


def solve():
	n = int(input())
	l = [*range(1, n + 1)]
	l.reverse()
	if n == 3:
		s = [[3, 2, 1], [1, 3, 2], [3, 1, 2]]
		for i in s:
			print(*i)
		return
	for i in range(n):
		temp = l[-1]
		l = [temp] + l[:n - 1]
		print(*l)
for _ in range(int(input())):
	solve()


t = int(input())
for i in range(t):
	n = int(input())
	lista = []
	for j in range(n):
		lista.append(j + 1)
	lista.reverse()
	if n == 3:
		print('3 2 1')
		print('1 3 2')
		print('3 1 2')
	else:
		for k in range(n):
			print(*lista)
			badas = lista[-1]
			lista.pop()
			lista.insert(0, badas)


t = int(input())
for _ in range(t):
	n = int(input())
	if n == 3:
		print('3 1 2\n2 3 1\n3 2 1')
		continue
	a = list('1243')
	for i in range(5, n + 1):
		a.append(i)
	i = 1
	while i <= n:
		print(*a[i:], *a[:i], sep=' ')
		i += 1


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


def deepcopy(l):
	temp = []
	for i in l:
		temp.append(i)
	return temp

def solution1(count):
	t = []
	t.append([1, 2, 3])
	t.append([2, 3, 1])
	t.append([2, 1, 3])
	if count == 3:
		return t
	for i in range(4, count + 1):
		for j in t:
			j.append(i)
		copy1 = t[-1]
		copy2 = deepcopy(copy1)
		(copy2[-1], copy2[-2]) = (copy2[-2], copy2[-1])
		t.append(copy2)
	return t

def check(ans):
	for i in range(len(ans) - 2):
		if ans[i] + ans[i + 1] == ans[i + 2]:
			return False
	return True
tc = int(input())
for i in range(tc):
	count = int(input())
	ans = solution1(count)
	for i in ans:
		i = i[::-1]
		print(*i)


for _ in range(int(input())):
	n = int(input())
	per = [i for i in range(n, 0, -1)]
	while n:
		print(*per)
		n -= 1
		(per[n], per[n - 1]) = (per[n - 1], per[n])


t = int(input())
for x in range(t):
	n = int(input())
	if n == 3:
		print('3 2 1')
		print('1 3 2')
		print('3 1 2')
	else:
		answer = [n - i for i in range(n)]
		for i in range(n):
			print(*answer)
			answer.append(answer.pop(0))


import math
from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	b = [int(i) for i in range(n, 0, -1)]
	res = 0
	for i in range(n):
		print(*b)
		(b[n - 1 - res], b[n - 2 - res]) = (b[n - 2 - res], b[n - 1 - res])
		res += 1


import sys

def input():
	return sys.stdin.readline()[:-1]

def solve():
	n = int(input())
	if n > 3:
		for i in range(n):
			print(*range(n - i, 0, -1), *range(n, n - i, -1))
	else:
		print(3, 2, 1)
		print(3, 1, 2)
		print(1, 3, 2)
t = int(input())
for __ in range(t):
	solve()


out = []
for _ in range(int(input())):
	n = int(input())
	if n == 3:
		print('3 2 1')
		print('1 3 2')
		print('3 1 2')
	else:
		a = [i for i in range(n, 0, -1)]
		for i in range(n):
			print(*a)
			a.insert(0, a.pop())


t = int(input())

def print_permut(permut):
	for x in permut:
		print(x, end=' ')
	print()

def testcase():
	n = int(input())
	permut = list(reversed([i for i in range(1, n + 1)]))
	print_permut(permut)
	for i in range(2, n + 1):
		rev = n - i
		(permut[rev + 1], permut[rev]) = (permut[rev], permut[rev + 1])
		print_permut(permut)
for x in range(t):
	testcase()


for _ in range(int(input())):
	nn = int(input())
	if nn == 3:
		print('3 2 1\n1 3 2\n3 1 2')
		continue
	l = [i for i in range(nn, 0, -1)]
	print(*l)
	j = 0
	for i in range(nn - 1):
		l.append(l[j])
		print(*l[j + 1:])
		j += 1


def fun():
	n = int(input())
	if n == 3:
		print(*[3, 2, 1])
		print(*[3, 1, 2])
		print(*[1, 3, 2])
		return
	arr = [i for i in range(n, 0, -1)]
	for i in range(n):
		print(*arr)
		arr = arr[-1:] + arr[:-1]
for _ in range(int(input())):
	fun()


def AbhiSolveKiya(n):
	a = [[1, 3, 2], [3, 2, 1], [3, 1, 2], [2, 3, 1]]
	if n == 3:
		for i in range(3):
			print(*a[i])
		return
	count = 0
	for j in a:
		b = [i for i in range(4, n + 1)]
		for i in range(n - 3):
			c = b[i:] + b[:i] + j
			print(*c)
			count += 1
			if count == n:
				return
	return
for _ in range(int(input())):
	n = int(input())
	AbhiSolveKiya(n)


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


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


t = int(input())
for i in range(t):
	n = int(input())
	nums = []
	for j in range(n, 0, -1):
		nums.append(j)
	print(*nums)
	for k in range(n - 1, 0, -1):
		l = nums[k]
		nums[k] = nums[k - 1]
		nums[k - 1] = l
		print(*nums)


import math
for _ in range(int(input())):
	n = int(input())
	l = [x + 1 for x in range(n)]
	l.reverse()
	print(*l)
	for i in range(n - 1):
		x = l + []
		xx = x[i]
		x[i] = x[i + 1]
		x[i + 1] = xx
		print(*x)


from itertools import permutations
l = list(permutations(range(1, 5 + 1)))
l2 = []
for i in l:
	l1 = i
	flag = False
	for i1 in range(2, len(l1)):
		s = l1[i1 - 1] + l1[i1 - 2]
		if l1[i1] == s:
			flag = True
			break
	if flag == False:
		l2.append(list(i))
for _ in range(int(input())):
	n = int(input())
	if n == 3:
		print('3 2 1')
		print('1 3 2')
		print('3 1 2')
	elif n == 4:
		print('4 3 2 1')
		print('1 2 4 3')
		print('3 4 1 2')
		print('2 4 1 3')
	elif n == 5:
		for i in range(5):
			print(*l2[i])
	else:
		ans = []
		for i in range(n, 5, -1):
			ans.append(i)
		for i in range(n):
			ans1 = ans + l2[i]
			print(*ans1)


def printPerm(n, arr, choices, k):
	if len(res) == n:
		return
	if k == n:
		res.append(arr)
	if k < 2:
		for (i, ch) in enumerate(choices):
			arr[k] = choices[i]
			printPerm(n, arr[:], choices[:i] + choices[i + 1:], k + 1)
	else:
		for (i, ch) in enumerate(choices):
			if ch != arr[k - 1] + arr[k - 2]:
				arr[k] = ch
				printPerm(n, arr[:], choices[:i] + choices[i + 1:], k + 1)
	return
for _ in range(int(input())):
	n = int(input())
	res = []
	printPerm(n, [0] * n, [i + 1 for i in range(n)], 0)
	for arr in res:
		print(' '.join(map(str, arr)))


test = int(input())
for i in range(test):
	n = int(input())
	l = []
	for i in range(1, n + 1):
		l.append(i)
	l.sort(reverse=True)
	for i in range(1, n + 1):
		k = n - i
		l.remove(1)
		l.insert(k, 1)
		print(*l)


from itertools import permutations
log = []
perms = permutations([str(i) for i in range(5, 0, -1)])
c = 0
for perm in perms:
	good = True
	for i in range(2, 5):
		if int(perm[i]) == int(perm[i - 1]) + int(perm[i - 2]):
			good = False
	if good:
		log.append(perm)
		c += 1
for _ in range(int(input())):
	n = int(input())
	if n > 5:
		base = [str(i) for i in range(n, 5, -1)]
		for indx in range(n):
			print(*base, *log[indx])
	else:
		for indx in range(n):
			print(*log[indx][-n:])


def solve():
	n = int(input())
	arr = [i for i in range(n, 0, -1)]
	if n == 3:
		print(3, 2, 1)
		print(2, 3, 1)
		print(3, 1, 2)
	else:
		for i in range(n):
			print(*arr)
			arr.insert(0, arr.pop())
tst = int(input())
for i in range(tst):
	solve()


import sys
input = sys.stdin.readline
from math import ceil, floor, gcd

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

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

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

def st():
	return input().rstrip('\n')

def isPrime(n):
	if n == 1:
		return 0
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return 0
	return 1
t = inp()
for _ in range(t):
	n = inp()
	a = [i for i in range(1, n + 1)]
	a = a[::-1]
	c = a[:]
	print(*a)
	for i in range(n - 2):
		a = c[-i - 1:] + c[:-i - 1]
		print(*a)
	(c[-1], c[-2]) = (c[-2], c[-1])
	print(*c)


T = int(input())
for _ in range(T):
	n = int(input())
	if n == 3:
		print('3 2 1')
		print('1 3 2')
		print('3 1 2')
	else:
		myper = list(range(n, 0, -1))
		for i in range(n):
			print(*myper)
			l = myper[-1]
			myper.pop()
			myper.insert(0, l)


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
sys.setrecursionlimit(100000000)
inp = lambda : int(input())
strng = lambda : input().strip()
jn = lambda x, l: x.join(map(str, l))
strl = lambda : list(input().strip())
mul = lambda : map(int, input().strip().split())
mulf = lambda : map(float, input().strip().split())
seq = lambda : list(map(int, input().strip().split()))
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))
mod = 1000000007
t = inp()
for j in range(t):
	n = inp()
	l = [i for i in range(n, 1, -1)] + [1]
	print(*l)
	for i in range(n - 1):
		(l[i], l[i + 1]) = (l[i + 1], l[i])
		print(*l)
		(l[i], l[i + 1]) = (l[i + 1], l[i])


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


t = int(input())
for j in range(t):
	n = int(input())
	d = list((x for x in range(n, 0, -1)))
	for i in range(n):
		k = d[0 + i:n + i] + d[:i]
		if k[0] + k[1] == k[2]:
			(k[2], k[1]) = (k[1], k[2])
		print(*k)


for _ in range(int(input())):
	n = int(input())
	p = list(range(1, n + 1))
	for i in range(0, n):
		x = p.copy()
		del x[i]
		print(p[i], *sorted(x, reverse=True))


import sys
from os import path
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
for index in range(int(input())):
	n = int(input())
	arr = [i for i in range(1, n + 1)][::-1]
	for i in range(n):
		print(*[arr[i]] + arr[:i] + arr[i + 1:])


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


for x in range(int(input())):
	lists = [x for x in range(1, int(input()) + 1)][::-1]
	for x in lists:
		print(*[x] + lists[:lists.index(x)] + lists[lists.index(x) + 1:])


for i in range(int(input())):
	n = int(input())
	a = list()
	for i in range(n, 0, -1):
		a.append(i)
	if n == 3:
		print('3 1 2')
		print('2 3 1')
		print('3 2 1')
	else:
		for i in range(n):
			print(*a)
			a.append(a[0])
			a.pop(0)


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	ans = [i for i in range(n, 0, -1)]
	end = n - 1
	for i in range(n):
		print(*ans)
		(ans[end], ans[end - 1]) = (ans[end - 1], ans[end])
		end -= 1


import sys
import math
from collections import deque, defaultdict
input = sys.stdin.readline

def multiple():
	a = map(int, input().split())
	return a

def array():
	a = input().split()
	return a

def intarray():
	a = list(map(int, input().split()))
	return a

def nondec(a):
	n = len(a)
	if n == 1:
		return True
	for i in range(1, n):
		if a[i] >= a[i - 1]:
			continue
		else:
			return False
	return True

def solution():
	n = int(input())
	arr = []
	for i in reversed(range(1, n + 1)):
		arr.append(i)
	print(*arr)
	for i in range(n - 1):
		(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
		print(*arr)
		(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
	return
t = int(input())
for _ in range(t):
	solution()


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


from sys import stdin, stdout
import sys
import math
import itertools
from collections import defaultdict
sys.setrecursionlimit(10 ** 6)

def main():
	t = int(stdin.readline().strip())
	for j in range(1, t + 1):
		n = int(stdin.readline().strip())
		arr = [i + 1 for i in range(n - 1, -1, -1)]
		print(*arr)
		k = 0
		for i in range(n - 1):
			new_arr = arr.copy()
			(new_arr[k], new_arr[k + 1]) = (new_arr[k + 1], new_arr[k])
			print(*new_arr)
			k += 1
main()


from collections import deque
for kdk in range(int(input())):
	n = int(input())
	a = deque()
	for i in range(n):
		a.append(n - i)
	print(*a)
	(a[-1], a[-2]) = (a[-2], a[-1])
	print(*a)
	(a[-3], a[-2]) = (a[-2], a[-3])
	print(*a)
	x = n - 3
	(a[-3], a[-2], a[-1]) = (3, 2, 1)
	while x > 0:
		t = a.popleft()
		a.append(t)
		print(*a)
		x -= 1


import math
from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	if n == 3:
		print(3, 2, 1)
		print(1, 3, 2)
		print(3, 1, 2)
		continue
	a = []
	for i in range(n, 0, -1):
		a.append(i)
	print(*a)
	for _ in range(n - 1):
		a.insert(0, a[-1])
		a.pop()
		print(*a)


t = int(float(input()))
for _ in range(t):
	n = int(float(input()))
	arr = [i for i in range(1, n + 1)]
	arr.sort(reverse=True)
	c = n - 1
	for i in range(n):
		print(*arr)
		(arr[c], arr[c - 1]) = (arr[c - 1], arr[c])
		c -= 1