Как хорошо известно, задача APSP (поиск кратчайших путей между всеми парами вершин) тесно связана с min+ умножением матриц. Сегодня мы предлагаем вам решить следующую задачу:
По заданному $x$ постройте неориентированный невзвешенный связный граф (то есть веса всех рёбер равны 1), такой что $\sum_{i=1}^{n} \sum_{j=i+1}^{n} \operatorname{dis}(i, j) = x$. Здесь $\operatorname{dis}(i, j)$ обозначает длину кратчайшего пути между вершиной $i$ и вершиной $j$.
Эта задача, конечно, очень проста... К сожалению, ваши ресурсы ограничены, поэтому вам нужно найти граф с не более чем 85 вершинами, удовлетворяющий требованиям.
Входные данные
Один тест содержит несколько наборов данных.
В первой строке входных данных записано количество наборов данных $T$ ($1 \le T \le 2000$), содержащихся в этом тесте.
Для каждого набора данных в отдельной строке дано целое число $x$ ($1 \le x \le 10^5$), представляющее ограничение, которое необходимо выполнить. Гарантируется, что существует хотя бы один граф с не более чем 85 вершинами, удовлетворяющий условию.
Выходные данные
Для каждого набора данных в первой строке выведите количество использованных вами вершин $n$ ($2 \le n \le 85$). Затем выведите $n - 1$ строк, где $i$-я строка — это двоичная строка длины $n - i$. $j$-й символ $i$-й строки равен 1 тогда и только тогда, когда между вершиной $i$ и вершиной $i + j$ есть ребро.
Пример
Входные данные
4 1 3 6 8
Выходные данные
2 1 3 11 1 4 111 11 1 4 110 10 1