C. Как можно меньше ничьих
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Скоро состоится большой футбольный чемпионат! $$$n$$$ команд будут участвовать в нем, и каждая пара различных команд сыграет ровно один матч друг с другом.

У матча может быть два различных исхода:

  • матч может закончиться вничью, тогда обе команды получат по $$$1$$$ очку;
  • одна из команд может победить, тогда победившая команда получит $$$3$$$ очка, а проигравшая — $$$0$$$.

Счет команды — суммарное количество очков, полученное командой за все матчи, в которых она играла.

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

Ваша задача — найти ситуацию (выбрать результат каждой игры), в которой у всех команд одинаковый итоговый счет, а количество ничьих минимально возможно.

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

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

Затем следуют сами наборы входных данных. Каждый набор описывается одной строкой, содержащей целое число $$$n$$$ ($$$2 \le n \le 100$$$) — количество команд.

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

Для каждого набора входных данных выведите $$$\frac{n(n - 1)}{2}$$$ целых чисел, описывающих результаты игр в следующем порядке: первое число соответствует результату матча между командой $$$1$$$ и командой $$$2$$$, второе — между командой $$$1$$$ и командой $$$3$$$, затем $$$1$$$ и $$$4$$$, ..., $$$1$$$ и $$$n$$$, $$$2$$$ и $$$3$$$, $$$2$$$ и $$$4$$$, ..., $$$2$$$ и $$$n$$$, и так далее, до результата матча между командой $$$n - 1$$$ и командой $$$n$$$.

Число, соответствующее результату матча между командой $$$x$$$ и командой $$$y$$$, должно быть равно $$$1$$$, если побеждает команда $$$x$$$, $$$-1$$$, если побеждает команда $$$y$$$, или $$$0$$$, если матч заканчивается вничью.

Все команды должны иметь одинаковый итоговый счет, и количество ничьих должно быть минимально возможным. Если оптимальных ответов несколько — выведите любой из них. Можно показать, что всегда есть способ составить результаты игр так, что все команды имеют одинаковый итоговый счет.

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

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

Во втором наборе входных данных из примера команда $$$1$$$ побеждает команду $$$2$$$ (команда $$$1$$$ получает $$$3$$$ очка), команда $$$1$$$ проигрывает команде $$$3$$$ (команда $$$3$$$ получает $$$3$$$ очка), и команда $$$2$$$ выигрывает у команды $$$3$$$ (команда $$$2$$$ получает $$$3$$$ очка).