Som kjent har APSP-problemet (korteste veier mellom alle par) en dyp forbindelse med min+-matrisemultiplikasjon. I dag ønsker vi at du løser følgende problem:
Gitt $x$, konstruer en urettet uvektet sammenhengende graf (dvs. at alle kantvekter er 1) slik at $\sum_{i=1}^{n} \sum_{j=i+1}^{n} \operatorname{dis}(i, j) = x$. Her representerer $\operatorname{dis}(i, j)$ lengden på den korteste veien mellom node $i$ og node $j$.
Dette problemet er selvsagt svært enkelt ... Dessverre er ressursene dine begrenset, så du håper å finne en graf med høyst 85 noder som oppfyller kravene.
Inndata
Ett enkelt testtilfelle inneholder flere datasett.
Den første linjen i inndataene er antall datasett $T$ ($1 \le T \le 2000$), som representerer antall datasett i dette testtilfellet.
For hvert datasett er det én linje med et heltall $x$ ($1 \le x \le 10^5$), som representerer kravet som må tilfredsstilles. Det er garantert at det finnes minst én graf med høyst 85 noder som oppfyller betingelsen.
Utdata
For hvert datasett skal du på første linje skrive ut antall noder $n$ du brukte ($2 \le n \le 85$). Skriv deretter ut $n - 1$ linjer, der den $i$-te linjen er en binærstreng med lengde $n - i$. Det $j$-te tegnet på den $i$-te linjen er 1 hvis og bare hvis det er en kant mellom node $i$ og node $i + j$.
Eksempel
Inndata
4 1 3 6 8
Utdata
2 1 3 11 1 4 111 11 1 4 110 10 1