Wie allgemein bekannt ist, steht das APSP-Problem (Kürzeste Pfade zwischen allen Paaren) in engem Zusammenhang mit der min+-Matrizenmultiplikation. Heute möchten wir, dass du das folgende Problem löst:
Gegeben sei $x$. Konstruiere einen ungerichteten, ungewichteten zusammenhängenden Graphen (d. h., alle Kantengewichte sind 1), sodass $\sum_{i=1}^{n} \sum_{j=i+1}^{n} \operatorname{dis}(i, j) = x$ gilt. Hierbei bezeichnet $\operatorname{dis}(i, j)$ die Länge des kürzesten Pfades zwischen Knoten $i$ und Knoten $j$.
Dieses Problem ist sicherlich sehr einfach ... Leider sind deine Ressourcen begrenzt, sodass du einen Graphen mit höchstens 85 Knoten finden möchtest, der die Anforderungen erfüllt.
Eingabe
Ein einzelner Testfall enthält mehrere Datensätze.
Die erste Zeile der Eingabe enthält die Anzahl der Datensätze $T$ ($1 \le T \le 2000$), die angibt, wie viele Datensätze in diesem Testfall enthalten sind.
Für jeden Datensatz gibt es eine Zeile mit einer ganzen Zahl $x$ ($1 \le x \le 10^5$), welche die zu erfüllende Bedingung darstellt. Es wird garantiert, dass mindestens ein Graph mit höchstens 85 Knoten existiert, der die Bedingung erfüllt.
Ausgabe
Gib für jeden Datensatz in der ersten Zeile die Anzahl der verwendeten Knoten $n$ aus ($2 \le n \le 85$). Gib anschließend $n - 1$ Zeilen aus, wobei die $i$-te Zeile eine Binärzeichenkette der Länge $n - i$ ist. Das $j$-te Zeichen der $i$-ten Zeile ist genau dann 1, wenn eine Kante zwischen Knoten $i$ und Knoten $i + j$ existiert.
Beispiel
Eingabe
4 1 3 6 8
Ausgabe
2 1 3 11 1 4 111 11 1 4 110 10 1