Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Dr.D is now fond of matrices. He is particularly interested in Doofish Matrices. A Doofish Matrix of order $N$ is a matrix with $N$ rows (numbered $1$ through $N$) and $N$ columns (numbered $1$ through $N$) such that:
Each element of this matrix is an integer between $1$ and $2N-1$ inclusive.
For each $i$ and $j$ ($1 ≤ i ≤ N$, $1 ≤ j ≤ 2N-1$), the integer $j$ appears in the $i$-th row and/or in the $i$-th column.

Now, for a given $N$, Dr.D is wondering if there is a Doofish Matrix of order $N$. Find such a matrix or determine that it does not exist. If there are multiple solutions, you may find any one.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first and only line of each test case contains a single integer $N$.

------  Output ------
For each test case:
First, print a line containing the string "Hooray" if a Doofish Matrix of order $N$ exists or "Boo" if it does not.
If it exists, print $N$ more lines describing one such matrix. For each valid $i$, the $i$-th of these lines should contain $N$ space-separated integers ― the elements in the $i$-th row.

------  Constraints ------
$1 ≤ T ≤ 2,000$
$1 ≤ N ≤ 2,000$
the sum of $N^{2}$ over all test cases does not exceed $4 \cdot 10^{6}$

------  Subtasks ------
Subtask #1 (29 points): $N$ is a power of $2$

Subtask #2 (71 points): original constraints

----- Sample Input 1 ------ 
2

1

2
----- Sample Output 1 ------ 
Hooray

1

Hooray

3 1

2 3

Difficulty: VERY_HARD
Tags: Constructive algorithms

Starter code:

Solutions:
t = int(input())
while t > 0:
	n = int(input())
	if n == 1:
		print('Hooray')
		print(1)
	elif n % 2 == 1:
		print('Boo')
	else:
		l = list(range(1, n))
		mat = []
		for i in range(n):
			mat.append([0] * n)
		for i in range(1, n):
			mat[0][i] = l[i - 1]
			mat[i][0] = l[i - 1] + n - 1
		k = 1
		for i in range(1, n):
			c = (k + 1) % (n - 1)
			mat[i][n - 1] = l[k % (n - 1)]
			mat[n - 1][i] = mat[i][n - 1] + n - 1
			for j in range(i + 1, n - 1):
				mat[i][j] = l[c % (n - 1)]
				mat[j][i] = mat[i][j] + n - 1
				c = (c + 1) % (n - 1)
			k = (k + 2) % (n - 1)
		print('Hooray')
		for i in range(n):
			for j in range(n):
				if i == j:
					print(2 * n - 1, end=' ')
				else:
					print(mat[i][j], end=' ')
			print()
	t -= 1


from collections import deque

def round_robin(n):
	d = deque(range(n))
	l = []
	for i in range(n - 1):
		temp = []
		for j in range(n // 2):
			temp.append([d[j], d[-j - 1]])
		l.append(temp)
		(d[0], d[-1]) = (d[-1], d[0])
		d.rotate()
	return l
for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print('Hooray')
		print(1)
	elif n & 1:
		print('Boo')
	else:
		print('Hooray')
		l = round_robin(n)
		tem1 = 2 * n - 1
		mat = [[tem1 for i in range(n)] for j in range(n)]
		tem1 = 1
		tem2 = 2
		for i in l:
			for j in i:
				(r, c) = (j[0], j[1])
				mat[r][c] = tem1
				mat[c][r] = tem2
			tem1 += 2
			tem2 += 2
		for row in mat:
			print(*row)


from collections import deque

def round_robin_even(d, n):
	for i in range(n - 1):
		yield [[d[j], d[-j - 1]] for j in range(n // 2)]
		(d[0], d[-1]) = (d[-1], d[0])
		d.rotate()

def round_robin(n):
	d = deque(range(n))
	return list(round_robin_even(d, n))
for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print('Hooray')
		print(1)
	elif n & 1:
		print('Boo')
	else:
		print('Hooray')
		l = round_robin(n)
		tem1 = 2 * n - 1
		mat = [[tem1 for i in range(n)] for j in range(n)]
		tem1 = 1
		tem2 = 2
		for i in l:
			for j in i:
				(left, right) = (j[0], j[1])
				mat[left][right] = tem1
				mat[right][left] = tem2
			tem1 += 2
			tem2 += 2
		for i in range(n):
			for j in range(n):
				print(mat[i][j], end=' ')
			print()


import math
from collections import deque

def print_matrix(mat):
	for i in range(n):
		for j in range(n):
			print(f'{str(mat[i][j]).ljust(3)}', end=' ')
		print()
t = int(input())
for c in range(t):
	n = int(input())
	if n == 1:
		print('Hooray')
		print('1')
	elif n % 2 == 1:
		print('Boo')
	else:
		print('Hooray')
		sup = [i for i in range(1, n + 1)]
		mat = [[0 for i in range(n)] for j in range(n)]
		for i in range(1, n):
			mat[0][i] = i
		index = 1
		for i in range(1, n - 1):
			mat[i][n - 1] = sup[index]
			index = (index + 2) % (n - 1)
		for i in range(1, n - 1):
			index = mat[i][n - 1]
			for j in range(i + 1, n - 1):
				mat[i][j] = sup[index]
				index = (index + 1) % (n - 1)
		for i in range(1, n):
			for j in range(0, i):
				mat[i][j] = mat[j][i] + n - 1
		for i in range(n):
			for j in range(n):
				if i == j:
					mat[i][j] = 2 * n - 1
		print_matrix(mat)


t = int(input())
while t:
	n = int(input())
	if n == 1:
		print('Hooray')
		print('1')
	elif n % 2 == 1:
		print('Boo')
	elif n == 2:
		print('Hooray')
		print('3 1')
		print('2 3')
	else:
		a = []
		for i in range(n):
			a.append([0] * n)
		b = list(range(1, n))
		k = 1
		for i in range(1, n):
			a[0][i] = b[i - 1]
		for i in range(1, n):
			temp = k
			a[i][n - 1] = b[temp]
			if temp == n - 2:
				temp = 0
			else:
				temp += 1
			for j in range(i + 1, n - 1):
				a[i][j] = b[temp]
				if temp == n - 2:
					temp = 0
				else:
					temp += 1
			if k == n - 2:
				k = 1
			elif k == n - 3:
				k = 0
			else:
				k += 2
		for i in range(n):
			for j in range(i + 1):
				if i != j:
					a[i][j] = a[j][i] + n - 1
				else:
					a[i][j] = 2 * n - 1
		print('Hooray')
		for i in range(n):
			print(*a[i])
	t = t - 1


def prin(Arr):
	l = len(Arr)
	for i in range(l):
		for j in range(l):
			print(Arr[i][j], end=' ')
		print()
t = int(input())
for _ in range(t):
	n = int(input())
	if n == 1:
		print('Hooray')
		print(1)
	elif n % 2 == 1:
		print('Boo')
	else:
		print('Hooray')
		a = [[0] * n for i in range(n)]
		li1 = list(range(1, n))
		li2 = list(range(n, 2 * n))
		for i in range(n):
			a[i][i] = 2 * n - 1
		for i in range(1, n):
			a[0][i] = i
			a[i][0] = n + i - 1
		for i in range(1, n - 1):
			ind = (2 * i - 1) % (n - 1)
			for j in range(i + 1, n):
				In = (ind + j - i) % (n - 1)
				a[i][j] = li1[In]
				a[j][i] = li2[In]
			a[i][n - 1] = li1[ind]
			a[n - 1][i] = li2[ind]
		prin(a)


import sys
from collections import defaultdict
mod = 1000000007
T = 1
T = int(sys.stdin.readline())
for _ in range(T):
	n = int(sys.stdin.readline())
	if n == 1:
		sys.stdout.write('Hooray\n')
		sys.stdout.write('1\n')
		continue
	if n & 1:
		sys.stdout.write('Boo\n')
	else:
		a = [[0 for i in range(n)] for j in range(n)]
		x = (n << 1) - 1
		l = []
		for i in range(n):
			a[i][i] = x
			if i > 0:
				a[0][i] = i
				l.append(i)
		k = 1
		nn = n - 1
		for i in range(1, n - 1):
			a[i][nn] = l[k]
			t = 1
			for j in range(i + 1, n - 1):
				a[i][j] = l[(k + t) % nn]
				t += 1
			k = (k + 2) % nn
		for i in range(1, n):
			for j in range(i):
				a[i][j] = x - a[j][i]
		sys.stdout.write('Hooray\n')
		for i in range(n):
			for j in range(n):
				sys.stdout.write(str(a[i][j]) + ' ')
			sys.stdout.write('\n')


import sys
from collections import Counter
for _ in range(int(input())):
	n = int(input())
	mat = [[0] * n for i in range(n)]
	if n == 1:
		print('Hooray')
		print(1)
		continue
	if n % 2 == 1:
		print('Boo')
		continue
	for i in range(n):
		mat[i][i] = 2 * n - 1
	h1 = list(range(1, n))
	h2 = list(range(n, 2 * n - 1))
	for i in range(1, n):
		mat[0][i] = h1[i - 1]
		mat[i][0] = h2[i - 1]
	(p1, p2) = (0, 0)
	ls1 = [i for i in range(1, n)] * 3
	ls2 = [i for i in range(n, 2 * n - 1)] * 3
	for i in range(1, n):
		p1 += 2
		p2 += 2
		select1 = {key: False for key in range(1, n)}
		for j in range(n):
			select1[mat[j][i]] = True
		temp = p1
		for k in range(i + 1, n):
			while select1[ls1[temp]]:
				temp += 1
			if not select1[ls1[temp]]:
				mat[i][k] = ls1[temp]
			temp += 1
		select2 = {key: False for key in range(n, 2 * n - 1)}
		for j in range(n):
			select2[mat[i][j]] = True
		temp = p2
		for k in range(i + 1, n):
			while select2[ls2[temp]]:
				temp += 1
			if not select2[ls2[temp]]:
				mat[k][i] = ls2[temp]
			temp += 1
		tt = 0
		for z in range(20):
			tt += 1
	print('Hooray')
	for row in mat:
		print(' '.join([str(i) for i in row]))


import os
import functools
import sys
import collections
import statistics
import math as mt
for _ in range(int(input())):
	n = int(input())
	a = [[0 for col in range(n)] for row in range(n)]
	if n == 1:
		print('Hooray')
		print(1)
	elif n % 2 == 0:
		print('Hooray')
		for i in range(0, n):
			for j in range(0, n):
				if i < j:
					if i + j + 2 >= n + 2:
						a[i][j] = 2 * n + 1 - (i + j + 2)
					if i + j + 2 <= n + 1:
						a[i][j] = 2 + n - (i + j + 2)
				elif i > j:
					if i + j + 2 > n:
						a[i][j] = i + j + 1
					if i + j + 2 <= n:
						a[i][j] = i + j + n
				else:
					a[i][j] = 2 * n - 1
		if n >= 4:
			x = n - 2
			for i in range(1, n // 2):
				a[i][n - 1] = x
				x -= 2
			x = n - 1
			for i in range(n // 2, n - 1):
				a[i][n - 1] = x
				x -= 2
			x = n + 2
			for i in range(1, n // 2):
				a[i][0] = x
				x += 2
			x = n + 1
			for i in range(n // 2, n - 1):
				a[i][0] = x
				x += 2
		for i in range(n):
			for j in range(n):
				print(a[i][j], end=' ')
			print()
	else:
		print('Boo')


for _ in range(int(input())):
	n = int(input())
	maatrix = [[0 for col in range(n)] for row in range(n)]
	if n == 1:
		print('Hooray\n1')
	elif n % 2 == 0:
		print('Hooray')
		for i in range(0, n):
			for j in range(0, n):
				if i < j:
					if i + j + 2 >= n + 2:
						maatrix[i][j] = 2 * n + 1 - (i + j + 2)
					elif 6 < 2:
						you_are_noob = 1
					if i + j + 2 <= n + 1:
						maatrix[i][j] = 2 + n - (i + j + 2)
					elif 6 == 9:
						dick = -1
				elif i > j:
					if i + j + 2 > n:
						maatrix[i][j] = i + j + 1
					if i + j + 2 <= n:
						maatrix[i][j] = i + j + n
					elif 6 < 2:
						you_are_cyak = 1
					elif 6 < 2:
						you_are_fuckingbishhh = 1
				else:
					maatrix[i][j] = 2 * n - 1
					chutiya = 3
		if n >= 4:
			vr = n - 2
			for i in range(1, n // 2):
				maatrix[i][n - 1] = vr
				vr -= 2
			vr = n - 1
			for i in range(n // 2, n - 1):
				maatrix[i][n - 1] = vr
				vr -= 2
			vr = n + 2
			for i in range(1, n // 2):
				maatrix[i][0] = vr
				vr += 2
			vr = n + 1
			for i in range(n // 2, n - 1):
				maatrix[i][0] = vr
				vr += 2
		elif 3 < 2:
			fuck_you = -1
		else:
			fuck_you = 1
		for i in range(n):
			for j in range(n):
				print(maatrix[i][j], end=' ')
			print()
	else:
		print('Boo')


import os
import sys
import collections

def display(n):
	a = [[0 for col in range(n)] for row in range(n)]
	if n == 1:
		print('Hooray')
		print(1)
	elif n % 2 == 0:
		print('Hooray')
		for i in range(0, n):
			for j in range(0, n):
				if i < j:
					if i + j + 2 >= n + 2:
						a[i][j] = 2 * n + 1 - (i + j + 2)
					if i + j + 2 <= n + 1:
						a[i][j] = 2 + n - (i + j + 2)
				elif i > j:
					if i + j + 2 > n:
						a[i][j] = i + j + 1
					if i + j + 2 <= n:
						a[i][j] = i + j + n
				else:
					a[i][j] = 2 * n - 1
		if n >= 4:
			x = n - 2
			for i in range(1, n // 2):
				a[i][n - 1] = x
				x -= 2
			x = n - 1
			for i in range(n // 2, n - 1):
				a[i][n - 1] = x
				x -= 2
			x = n + 2
			for i in range(1, n // 2):
				a[i][0] = x
				x += 2
			x = n + 1
			for i in range(n // 2, n - 1):
				a[i][0] = x
				x += 2
		for i in range(n):
			for j in range(n):
				print(a[i][j], end=' ')
			print()
	else:
		print('Boo')
T = int(input())
for _ in range(T):
	n = int(input())
	display(n)


for _ in range(int(input())):
	n = int(input())
	array_matrix = [[0 for col in range(n)] for row in range(n)]
	if n == 1:
		print('Hooray\n1')
	elif n % 2 == 0:
		print('Hooray')
		for i in range(0, n):
			for j in range(0, n):
				if i < j:
					if i + j + 2 >= n + 2:
						array_matrix[i][j] = 2 * n + 1 - (i + j + 2)
					if i + j + 2 <= n + 1:
						array_matrix[i][j] = 2 + n - (i + j + 2)
				elif i > j:
					if i + j + 2 > n:
						array_matrix[i][j] = i + j + 1
					if i + j + 2 <= n:
						array_matrix[i][j] = i + j + n
				else:
					array_matrix[i][j] = 2 * n - 1
					fuck_you = 0
		if n >= 4:
			varrr = n - 2
			for i in range(1, n // 2):
				array_matrix[i][n - 1] = varrr
				varrr -= 2
			varrr = n - 1
			for i in range(n // 2, n - 1):
				array_matrix[i][n - 1] = varrr
				varrr -= 2
			varrr = n + 2
			for i in range(1, n // 2):
				array_matrix[i][0] = varrr
				varrr += 2
			varrr = n + 1
			for i in range(n // 2, n - 1):
				array_matrix[i][0] = varrr
				varrr += 2
		elif 3 < 2:
			fuck_you = -1
		else:
			fuck_you = 1
		for i in range(n):
			for j in range(n):
				print(array_matrix[i][j], end=' ')
			print()
	else:
		print('Boo')


for _ in range(int(input())):
	n = int(input())
	a = [[0 for col in range(n)] for row in range(n)]
	if n == 1:
		print('Hooray')
		print(1)
	elif n % 2 == 0:
		print('Hooray')
		for i in range(0, n):
			for j in range(0, n):
				if i < j:
					if i + j + 2 >= n + 2:
						a[i][j] = 2 * n + 1 - (i + j + 2)
					if i + j + 2 <= n + 1:
						a[i][j] = 2 + n - (i + j + 2)
				elif i > j:
					if i + j + 2 > n:
						a[i][j] = i + j + 1
					if i + j + 2 <= n:
						a[i][j] = i + j + n
				else:
					a[i][j] = 2 * n - 1
		if n >= 4:
			x = n - 2
			for i in range(1, n // 2):
				a[i][n - 1] = x
				x -= 2
			x = n - 1
			for i in range(n // 2, n - 1):
				a[i][n - 1] = x
				x -= 2
			x = n + 2
			for i in range(1, n // 2):
				a[i][0] = x
				x += 2
			x = n + 1
			for i in range(n // 2, n - 1):
				a[i][0] = x
				x += 2
		for i in range(n):
			for j in range(n):
				print(a[i][j], end=' ')
			print()
	else:
		print('Boo')


def func(n):
	teams = [_ for _ in range(1, n + 1)]
	n = n // 2
	stages = []
	for i in range(len(teams) - 1):
		t = teams[:1] + teams[-i:] + teams[1:-i] if i else teams
		stages.append(list(zip(t[:n], reversed(t[n:]))))
	return stages

def getMatrix(n):
	a = [[0 for _ in range(0, n + 1)] for _ in range(0, n + 1)]
	d = 2 * n - 1
	for i in range(1, n + 1):
		a[i][i] = d
	return a
t = int(input())
for _ in range(t):
	n = int(input())
	if n & 1 and n > 1:
		print('Boo')
		continue
	print('Hooray')
	a = getMatrix(n)
	stages = func(n)
	cnt = 1
	for x in stages:
		for y in x:
			a[y[0]][y[1]] = cnt
			a[y[1]][y[0]] = cnt + 1
		cnt += 2
	for x in a[1:]:
		for i in range(1, n + 1):
			print(x[i], end=' ')
		print()


from itertools import *
from collections import *
from sys import *

def input():
	return stdin.readline()

def two(n1):
	chess = [[0 for i in range(n1)] for i in range(n1)]
	teams = [i for i in range(1, n1 + 1)]
	n = int(len(teams) / 2)
	stages = []
	c = 1
	for i in range(len(teams) - 1):
		t = teams[:1] + teams[-i:] + teams[1:-i] if i else teams
		for j in list(zip(t[:n], reversed(t[n:]))):
			chess[j[0] - 1][j[1] - 1] = c
			chess[j[1] - 1][j[0] - 1] = c + (n1 - 1)
		c += 1
	for i in range(n1):
		chess[i][i] = 2 * n1 - 1
	for i in chess:
		print(*i)
for _ in range(int(input())):
	n = int(input())
	if n % 2 and n != 1:
		print('Boo')
	else:
		print('Hooray')
		two(n)


for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print('Hooray')
		print(1)
	elif n % 2 == 1:
		print('Boo')
	elif n == 2:
		print('Hooray')
		print('3 1')
		print('2 3')
	else:
		a = []
		for i in range(n):
			a.append([0] * n)
		l = list(range(1, n))
		for j in range(1, n):
			a[0][j] = l[j - 1]
		k = 1
		for i in range(1, n):
			temp = k
			a[i][n - 1] = l[temp]
			if temp == n - 2:
				temp = 0
			else:
				temp += 1
			for j in range(i + 1, n - 1):
				a[i][j] = l[temp]
				if temp == n - 2:
					temp = 0
				else:
					temp += 1
			if k == n - 2:
				k = 1
			elif k == n - 3:
				k = 0
			else:
				k += 2
		for i in range(n):
			for j in range(0, i + 1):
				if i == j:
					a[i][j] = 2 * n - 1
				else:
					a[i][j] = a[j][i] + n - 1
		print('Hooray')
		for i in range(n):
			print(*a[i])


for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print('Hooray\n1')
	elif n % 2:
		print('Boo')
	else:
		end = 2 * n - 1
		print('Hooray')
		l = [[end for i in range(n)] for i in range(n)]
		t = 2 * n - 2
		for i in range(1, n):
			(s, la) = (i, i)
			l[i - 1][n - 1] = i
			l[n - 1][i - 1] = t
			for j in range(n // 2 - 1):
				s -= 1
				la += 1
				if s < 1:
					s = n - 1
				la = la % (n - 1)
				if la == 0:
					la = n - 1
				l[min(s, la) - 1][max(s, la) - 1] = i
				l[max(s, la) - 1][min(s, la) - 1] = t
			t -= 1
		for i in l:
			print(*i)


import copy
import sys
for _ in range(int(input())):
	n = int(input())
	mat = [[0] * n for i in range(n)]
	if n == 1:
		print('Hooray')
		print(1)
		continue
	if (n * n - n) % (2 * n - 2):
		print('Boo')
		continue
	for i in range(n):
		mat[i][i] = 2 * n - 1
	h1 = list(range(1, n))
	h2 = list(range(n, 2 * n - 1))
	for i in range(1, n):
		mat[0][i] = h1[i - 1]
		mat[i][0] = h2[i - 1]
	p1 = 0
	p2 = 0
	ls1 = [i for i in range(1, n)] * 3
	ls2 = [i for i in range(n, 2 * n - 1)] * 3
	for i in range(1, n):
		p1 += 2
		p2 += 2
		check1 = {key: False for key in range(1, n)}
		for j in range(n):
			check1[mat[j][i]] = True
		tm = p1
		for k in range(i + 1, n):
			while check1[ls1[tm]]:
				tm += 1
			if not check1[ls1[tm]]:
				mat[i][k] = ls1[tm]
			tm += 1
		check2 = {key: False for key in range(n, 2 * n - 1)}
		for j in range(n):
			check2[mat[i][j]] = True
		tm = p2
		for k in range(i + 1, n):
			while check2[ls2[tm]]:
				tm += 1
			if not check2[ls2[tm]]:
				mat[k][i] = ls2[tm]
			tm += 1
	print('Hooray')
	for row in mat:
		print(' '.join([str(i) for i in row]))


t = int(input())
for i in range(t):
	n = int(input())
	if n == 1:
		print('Hooray')
		print(1)
	elif n % 2 == 1:
		print('Boo')
	else:
		print('Hooray')
		arr = []
		for i in range(n):
			ok = [0] * (n + 2)
			arr.append(ok)
		for i in range(1, n):
			next = i + 1
			if next == n:
				next = 1
			prev = i - 1
			if prev == 0:
				prev = n - 1
			arr[i - 1][n - 1] = i
			cnt = 0
			while cnt != n / 2 - 1:
				arr[min(next, prev) - 1][max(next, prev) - 1] = i
				next += 1
				if next == n:
					next = 1
				prev -= 1
				if prev == 0:
					prev = n - 1
				cnt += 1
		for i in range(n):
			arr[i][i] = 2 * n - 1
		for i in range(n):
			for j in range(i + 1, n):
				arr[j][i] = arr[i][j] + n - 1
		for i in range(n):
			for j in range(n):
				print(arr[i][j], end=' ')
			print()


def solve(n):
	a = [[0 for _ in range(n)] for _ in range(n)]
	for i in range(n):
		a[i][i] = 2 * n - 1
	for k in range(1, n):
		a[k - 1][n - 1] = k
		a[n - 1][k - 1] = k + n - 1
		(i, j) = (k, k)
		for _ in range(n // 2 - 1):
			i += 1
			if i == n:
				i = 1
			j -= 1
			if j == 0:
				j = n - 1
			if i < j:
				a[i - 1][j - 1] = k
				a[j - 1][i - 1] = k + n - 1
			else:
				a[j - 1][i - 1] = k
				a[i - 1][j - 1] = k + n - 1
	for i in range(n):
		print(*a[i])
for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print('Hooray')
		print(1)
	elif n % 2 == 1:
		print('Boo')
	else:
		print('Hooray')
		solve(n)


from math import factorial as fac
import sys, math
f = None
try:
	f = open('q1.input', 'r')
except IOError:
	f = sys.stdin

def read_int():
	return int(f.readline())

def read_int_array():
	return [int(x) for x in f.readline().split(' ')]

def rns():
	a = [x for x in f.readline().split(' ')]
	return (int(a[0]), a[1].strip())

def read_string():
	return list(f.readline())
NUMBER = 10 ** 9 + 7

def factorial(n):
	M = 1000000007
	f = 1
	for i in range(1, n + 1):
		f = f * i % M
	return f

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m
from collections import defaultdict

def is_valid(x, d):
	for y in d:
		if y == x:
			if 0 not in d or y == 0:
				if d[x] != 2:
					return False
				continue
			if d[0] != d[y] - 2:
				return False
			continue
		if x - y not in d:
			return False
		if d[x - y] != d[y]:
			return False
	return True

def solution(N):
	if N > 1 and N % 2:
		print('Boo')
		return
	print('Hooray')
	A = [[0 for i in range(N)] for j in range(N)]
	for i in range(N):
		A[i][i] = 2 * N - 1
	for i in range(N - 1):
		shunned = (N - 1 + i) // 2 if i % 2 else i // 2
		for j in range(N - 1):
			if j == shunned:
				continue
			couple = (j, (i - j) % (N - 1))
			A[couple[0]][couple[1]] = 2 * i + 1
			A[couple[1]][couple[0]] = 2 * i + 2
		A[N - 1][shunned] = 2 * i + 1
		A[shunned][N - 1] = 2 * i + 2
	for i in range(N):
		print(' '.join(map(str, A[i])))
	return

def main():
	T = read_int()
	for i in range(T):
		N = read_int()
		solution(N)
main()


def p(arr):
	if arr is None:
		print('Boo')
		return
	print('Hooray')
	for row in arr:
		print(' '.join(list(map(str, row))))
t = int(input())
for ii in range(t):
	n = int(input())
	if n == 1:
		arr = [[1]]
		p(arr)
		continue
	if n & 1:
		p(None)
		continue
	if n == 2:
		arr = [[3, 1], [2, 3]]
		p(arr)
		continue
	m = n // 2
	arr = [[None for i in range(n)] for j in range(n)]
	l = [2 * i for i in range(1, m)] + [2 * (m - i) - 1 for i in range(m)]
	for i in range(n - 1):
		ind = i + 1
		arr[0][l[-1]] = ind
		for j in range(m - 1):
			arr[l[j]][l[2 * (m - 1) - 1 - j]] = ind
		l = l[1:] + [l[0]]
	for i in range(n):
		arr[i][i] = n
	for i in range(n):
		for j in range(n):
			if arr[i][j] is None:
				arr[i][j] = n + arr[j][i]
	p(arr)