Як добре відомо, задача 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