A. MEX на матрице
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны $$$n^2$$$ карточек со значениями от $$$0$$$ до $$$n^2-1$$$. Вам необходимо расположить их в ячейках матрицы размера $$$n$$$ на $$$n$$$, так чтобы в каждой ячейке находилась ровно одна карточка.

MEX (минимальное исключенное значение) подматрицы$$$^{\text{∗}}$$$ определяется как наименьшее целое неотрицательное число, которое не встречается в подматрице.

Ваша задача — расположить карточки так, чтобы сумма значений MEX по всем $$$\left(\frac{n(n+1)}{2}\right)^2$$$ подматрицам была максимальной.

$$$^{\text{∗}}$$$Подматрица матрицы размером $$$n$$$ на $$$n$$$ задается четыремя индексами $$$l_1, r_1, l_2, r_2$$$, удовлетворяющими $$$1\le l_1\le r_1\le n$$$ и $$$1\le l_2\le r_2\le n$$$. Элемент в $$$i$$$-й стррке и $$$j$$$-м столбце матрицы принадлежит подматрице, если и только если $$$l_1\le i\le r_1$$$ и $$$l_2\le j\le r_2$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1\le n\le 500$$$) — длина стороны квадратной матрицы.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$1000$$$.

Выходные данные

Для каждого набора входных данных выведите $$$n$$$ строк, каждая из которых содержит $$$n$$$ целых чисел, представляющих элементы матрицы.

Если есть несколько решений, вы можете вывести любое из них.

Пример
Входные данные
2
2
3
Выходные данные
0 1 
2 3 
8 4 5 
6 0 1 
7 2 3
Примечание

В первом наборе входных данных одно из допустимых расположений:

01
23

Всего имеется $$$9$$$ подматриц, и $$$4$$$ из них с ненулевым MEX показаны ниже:

0
значения:$$$[0]$$$ — MEX: $$$1$$$

01
значения:$$$[0, 1]$$$  — MEX: $$$2$$$

0
2
значения:$$$[0, 2]$$$  — MEX: $$$1$$$

01
23
значения:$$$[0, 1, 2, 3]$$$  — MEX: $$$4$$$

Сумма MEX по всем подматрицам составляет $$$1+2+1+4 = 8$$$.

Можно показать, что другие расположения не имеют большей суммы значений MEX.