よく知られているように、APSP(全点対最短経路)問題は min+ 行列積と深い関わりがあります。今日、あなたに解いてほしい問題は以下の通りです。
$x$ が与えられるので、$\sum_{i=1}^{n} \sum_{j=i+1}^{n} \operatorname{dis}(i, j) = x$ を満たす無向重みなし連結グラフ(すなわち、すべての辺の重みが 1 であるグラフ)を構築してください。ここで、$\operatorname{dis}(i, j)$ は頂点 $i$ と頂点 $j$ の間の最短経路長を表します。
この問題は非常に簡単です……残念ながら、あなたのリソースは限られているため、頂点数が 85 以下の条件を満たすグラフを見つける必要があります。
入力
1 つのテストケースには複数のデータセットが含まれます。
入力の 1 行目はデータセットの個数 $T$ ($1 \le T \le 2000$) であり、このテストケースに含まれるデータセットの数を表します。
各データセットについて、満たすべき制約を表す整数 $x$ ($1 \le x \le 10^5$) が 1 行に与えられます。条件を満たす頂点数 85 以下のグラフが少なくとも 1 つ存在することが保証されます。
出力
各データセットについて、1 行目に使用した頂点数 $n$ ($2 \le n \le 85$) を出力してください。続いて $n - 1$ 行を出力し、そのうち $i$ 行目には長さ $n - i$ の 2 進文字列を出力してください。$i$ 行目の $j$ 番目の文字は、頂点 $i$ と頂点 $i + j$ の間に辺が存在するとき、かつそのときに限り 1 となります。
入出力例
入力
4 1 3 6 8
出力
2 1 3 11 1 4 111 11 1 4 110 10 1