B. Яркая, красивая, блистательная
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть пирамида, состоящая из $$$n$$$ этажей. Этажи пронумерованы сверху вниз. Так как это пирамида, то на $$$i$$$-м этаже $$$i$$$ комнат.

Будем обозначать $$$j$$$-ю комнату на $$$i$$$-м этаже как $$$(i,j)$$$. Для всех положительных чисел $$$i$$$ и $$$j$$$ таких, что $$$1 \le j \le i < n$$$, существуют $$$2$$$ односторонние лестницы, ведущие из комнаты $$$(i,j)$$$ в $$$(i+1,j)$$$, а также из комнаты $$$(i,j)$$$ в $$$(i+1,j+1)$$$ соответственно.

Вы выбираете для каждой комнаты, разместить там факел или оставить комнату пустой. Определим яркость комнаты $$$(i, j)$$$ как количество комнат с факелами, из которых можно попасть в комнату $$$(i, j)$$$, используя неотрицательное число лестниц.

Например, если $$$n=5$$$ и факелы расположены в комнатах $$$(1,1)$$$, $$$(2,1)$$$, $$$(3,2)$$$, $$$(4,1)$$$, $$$(4,3)$$$ и $$$(5,3)$$$, то пирамида выглядит следующим образом:

На рисунке выше комнаты с факелами отмечены желтым, пустые — белым. Синие числа в правом нижнем углу показывают яркость комнат.

Комната $$$(4,2)$$$ (отмечена звездой на рисунке ниже) имеет яркость $$$3$$$. Комнаты, из которых вы можете попасть в комнату $$$(4,2)$$$, имеют красную границу. Яркость равна $$$3$$$, так как в этих комнатах три факела.

Пирамида называется красивой, если и только если для каждого этажа все комнаты на этом этаже имеют одинаковую яркость.

Определим блистательность красивой пирамиды как сумму значений яркости в комнатах $$$(1,1)$$$, $$$(2,1)$$$, $$$(3,1)$$$, ..., $$$(n,1)$$$.

Расположите факелы в пирамиде таким образом, чтобы пирамида оказалась красивой, а ее блистательность была максимально возможной.

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

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

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

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

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

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

Для каждого набора входных данных выведите $$$n$$$ строк — расположение факелов в пирамиде.

В $$$i$$$-й строке выведите $$$i$$$ чисел, разделенных пробелами. $$$j$$$-е число в $$$i$$$-й строке должно быть равно $$$1$$$, если в комнате $$$(i,j)$$$ есть факел, и $$$0$$$ иначе.

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

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

В третьем наборе входных данных факелы размещены в комнатах $$$(1,1)$$$, $$$(2,1)$$$, $$$(2,2)$$$, $$$(3,1)$$$ и $$$(3,3)$$$.

Пирамида красивая, так как на каждом этаже все комнаты имеют одинаковую яркость. Например, все комнаты на третьем этаже имеют яркость $$$3$$$.

Блистательность пирамиды равна $$$1+2+3 = 6$$$. Можно показать, что не существует расположения факелов для $$$n=3$$$ с большей блистетельностью.