Som bekant har APSP-problemet (kortaste vägar mellan alla par) en djup koppling till min+-matrismultiplikation. Idag vill vi att du löser följande problem:
Givet $x$, konstruera en oriktad oviktad sammanhängande graf (dvs. alla kantvikter är 1) sådan att $\sum_{i=1}^{n} \sum_{j=i+1}^{n} \operatorname{dis}(i, j) = x$. Här representerar $\operatorname{dis}(i, j)$ längden på den kortaste vägen mellan nod $i$ och nod $j$.
Detta problem är naturligtvis väldigt enkelt... Tyvärr är dina resurser begränsade, så du hoppas kunna hitta en graf med högst 85 noder som uppfyller kraven.
Indata
Ett enskilt testfall innehåller flera datamängder.
Den första raden i indatan är antalet datamängder $T$ ($1 \le T \le 2000$), vilket representerar antalet datamängder som ingår i detta testfall.
För varje datamängd finns en rad med ett heltal $x$ ($1 \le x \le 10^5$), vilket representerar villkoret som måste uppfyllas. Det garanteras att det finns minst en graf med högst 85 noder som uppfyller villkoret.
Utdata
För varje datamängd, skriv på första raden ut antalet noder $n$ som du använde ($2 \le n \le 85$). Skriv sedan ut $n - 1$ rader, där den $i$:te raden är en binär sträng med längden $n - i$. Det $j$:te tecknet på den $i$:te raden är 1 om och endast om det finns en kant mellan nod $i$ och nod $i + j$.
Exempel
Indata
4 1 3 6 8
Utdata
2 1 3 11 1 4 111 11 1 4 110 10 1