Jak powszechnie wiadomo, problem APSP (najkrótszych ścieżek między wszystkimi parami wierzchołków) ma głęboki związek z mnożeniem macierzy typu min+. Dzisiaj chcemy, abyś rozwiązał następujące zadanie:
Mając dane $x$, skonstruuj nieskierowany, nieważony graf spójny (tzn. wagi wszystkich krawędzi wynoszą 1) taki, że $\sum_{i=1}^{n} \sum_{j=i+1}^{n} \operatorname{dis}(i, j) = x$. Tutaj $\operatorname{dis}(i, j)$ oznacza długość najkrótszej ścieżki między wierzchołkiem $i$ a wierzchołkiem $j$.
To zadanie jest oczywiście bardzo proste... Niestety Twoje zasoby są ograniczone, więc masz nadzieję znaleźć spełniający wymagania graf o co najwyżej 85 wierzchołkach.
Wejście
Pojedynczy przypadek testowy zawiera wiele zestawów danych.
Pierwszy wiersz wejścia zawiera liczbę zestawów danych $T$ ($1 \le T \le 2000$), oznaczającą liczbę zestawów danych zawartych w tym przypadku testowym.
Dla każdego zestawu danych w jednym wierszu znajduje się liczba całkowita $x$ ($1 \le x \le 10^5$), oznaczająca warunek, który należy spełnić. Gwarantuje się, że istnieje co najmniej jeden graf o co najwyżej 85 wierzchołkach spełniający ten warunek.
Wyjście
Dla każdego zestawu danych wypisz w pierwszym wierszu liczbę użytych wierzchołków $n$ ($2 \le n \le 85$). Następnie wypisz $n - 1$ wierszy, gdzie $i$-ty wiersz to ciąg binarny o długości $n - i$. $j$-ty znak $i$-tego wiersza jest równy 1 wtedy i tylko wtedy, gdy istnieje krawędź między wierzchołkiem $i$ a wierzchołkiem $i + j$.
Przykład
Wejście
4 1 3 6 8
Wyjście
2 1 3 11 1 4 111 11 1 4 110 10 1