Come è ben noto, il problema APSP (cammini minimi tra tutte le coppie) ha un profondo legame con la moltiplicazione di matrici min+. Oggi vogliamo che tu risolva il seguente problema:
Dato $x$, costruisci un grafo connesso non orientato e non pesato (cioè tutti i pesi degli archi sono pari a 1) tale che $\sum_{i=1}^{n} \sum_{j=i+1}^{n} \operatorname{dis}(i, j) = x$. Qui, $\operatorname{dis}(i, j)$ rappresenta la lunghezza del cammino minimo tra il nodo $i$ e il nodo $j$.
Questo problema è certamente molto semplice... Sfortunatamente, le tue risorse sono limitate, quindi speri di trovare un grafo con non più di 85 nodi che soddisfi i requisiti.
Input
Un singolo caso di test contiene più set di dati.
La prima riga dell'input è il numero di set di dati $T$ ($1 \le T \le 2000$), che rappresenta il numero di set di dati contenuti in questo caso di test.
Per ogni set di dati, c'è una riga con un intero $x$ ($1 \le x \le 10^5$), che rappresenta il vincolo da soddisfare. È garantito che esista almeno un grafo con non più di 85 nodi che soddisfa la condizione.
Output
Per ogni set di dati, stampa sulla prima riga il numero di nodi $n$ che hai utilizzato ($2 \le n \le 85$). Poi stampa $n - 1$ righe, dove la $i$-esima riga è una stringa binaria di lunghezza $n - i$. Il $j$-esimo carattere della $i$-esima riga è 1 se e solo se esiste un arco tra il nodo $i$ e il nodo $i + j$.
Esempio
Input
4 1 3 6 8
Output
2 1 3 11 1 4 111 11 1 4 110 10 1