众所周知，APSP（全源最短路）问题与 min+ 矩阵乘法有着深刻的联系。今天，我们希望你解决以下问题：

给定 $x$，构造一个无向无权连通图（即所有边权均为 1），使得 $\sum_{i=1}^{n} \sum_{j=i+1}^{n} \text{dis}(i, j) = x$。这里，$\text{dis}(i, j)$ 表示节点 $i$ 和节点 $j$ 之间的最短路径长度。

这个问题当然非常简单……不幸的是，你的资源有限，因此你希望找到一个节点数不超过 85 的满足要求的图。

输入格式

单个测试用例包含多个数据集。

输入的第一行是数据集的数量 $T$ ($1 \le T \le 2000$)，表示该测试用例中包含的数据集数量。

对于每个数据集，包含一行，有一个整数 $x$ ($1 \le x \le 10^5$)，表示需要满足的限制。保证存在至少一个节点数不超过 85 的图满足条件。

输出格式

对于每个数据集，第一行输出你使用的节点数 $n$ ($2 \le n \le 85$)。

然后输出 $n - 1$ 行，其中第 $i$ 行是一个长度为 $n - i$ 的二进制字符串。第 $i$ 行的第 $j$ 个字符为 1 当且仅当节点 $i$ 和节点 $i + j$ 之间存在一条边。

样例

输入样例 1

4
1
3
6
8

输出样例 1

2
1
3
11
1
4
111
11
1
4
110
10
1