Universal Cup Judging System

Universal Cup

시간 제한: 3.0 s 메모리 제한: 1024 MB 총점: 100 해킹 가능 ✓
통계

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

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.