F. Горячая матрица
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Свинка Чжоу любит матрицы, особенно те, которые вызывают у него восторг, называемые горячими матрицами.

Горячую матрицу размера $$$n \times n$$$ можно определить следующим образом. Пусть $$$a_{i, j}$$$ обозначает элемент в $$$i$$$-й строке, $$$j$$$-м столбце ($$$1 \le i, j \le n$$$).

  1. Каждый столбец и каждая строка матрицы содержат перестановку целых чисел от $$$0$$$ до $$$n-1$$$.
  2. Для всех пар индексов $$$i$$$, $$$j$$$ таких, что $$$1 \le i, j \le n$$$, выполняется $$$a_{i, j} + a_{i, n - j + 1} = n - 1$$$.
  3. Для всех пар индексов $$$i$$$, $$$j$$$ таких, что $$$1 \le i, j \le n$$$, выполняется $$$a_{i, j} + a_{n - i + 1, j} = n - 1$$$.
  4. Все упорядоченные пары $$$\left(a_{i, j}, a_{i, j + 1}\right)$$$, где $$$1 \le i \le n$$$, $$$1 \le j \lt n$$$, попарно различны.
  5. Все упорядоченные пары $$$\left(a_{i, j}, a_{i + 1, j}\right)$$$, где $$$1 \le i \lt n$$$, $$$1 \le j \le n$$$, попарно различны.

Свинка Чжоу дает вам число $$$n$$$. Вам нужно предоставить ему горячую матрицу, если такая горячая матрица существует для данного $$$n$$$, или сообщить ему, что он никогда не испытает восторг, если горячая матрица не существует для данного $$$n$$$.

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

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

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

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

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

Для каждого набора входных данных выведите «NO» (без кавычек), если горячей матрица не существует для данного $$$n$$$.

В противном случае выведите «YES» (без кавычек) в первой строке. Затем выведите $$$n$$$ строк, в каждой из них по $$$n$$$ чисел, представляющих горячую матрицу размера $$$n\times n$$$, которая соответствует требованиям задачи.

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

Пример
Входные данные
4
1
2
3
4
Выходные данные
YES
0
YES
0 1
1 0
NO
YES
0 1 2 3
1 3 0 2
2 0 3 1
3 2 1 0
Примечание

В первом наборе входных данных можно проверить, что матрица, представленная в примере, соответствует всем условиям, указанным в задаче.

Во втором наборе входных данных можно доказать, что не существует горячей матрицы, которая удовлетворяет условиям задачи.