Kuten hyvin tiedetään, APSP-ongelmalla (kaikkien solmuparien väliset lyhimmät polut) on syvä yhteys min+-matriisikertolaskuun. Tänään haluamme sinun ratkaisevan seuraavan ongelman:
Kun annetaan $x$, muodosta suuntaamaton painottamaton yhtenäinen verkko (eli kaikkien kaarien painot ovat 1) siten, että $\sum_{i=1}^{n} \sum_{j=i+1}^{n} \operatorname{dis}(i, j) = x$. Tässä $\operatorname{dis}(i, j)$ tarkoittaa solmun $i$ ja solmun $j$ välisen lyhimmän polun pituutta.
Tämä ongelma on tietysti hyvin yksinkertainen... Valitettavasti resurssisi ovat rajalliset, joten toivot löytäväsi vaatimukset täyttävän verkon, jossa on enintään 85 solmua.
Syöte
Yksi testitapaus sisältää useita tietoaineistoja.
Syötteen ensimmäinen rivi on tietoaineistojen lukumäärä $T$ ($1 \le T \le 2000$), joka ilmaisee tässä testitapauksessa olevien tietoaineistojen määrän.
Jokaista tietoaineistoa kohden on yksi rivi, jolla on kokonaisluku $x$ ($1 \le x \le 10^5$), joka kuvaa täytettävää rajoitetta. On taattua, että on olemassa ainakin yksi enintään 85 solmun verkko, joka täyttää ehdon.
Tuloste
Tulosta jokaista tietoaineistoa kohden ensimmäiselle riville käyttämiesi solmujen lukumäärä $n$ ($2 \le n \le 85$). Tulosta sen jälkeen $n - 1$ riviä, missä $i$:s rivi on pituudeltaan $n - i$ oleva binäärimerkkijono. Rivin $i$ merkki $j$ on 1 jos ja vain jos solmun $i$ ja solmun $i + j$ välillä on kaari.
Esimerkki
Syöte
4 1 3 6 8
Tuloste
2 1 3 11 1 4 111 11 1 4 110 10 1