Description

一个几年前刚刚和两个红方帅对抗完的黑卒正在二维平面上闲逛。

这时，他看见了一个 $n$ 行 $n$ 列的棋盘。

这个棋盘的某些格子是可以通过的，有些是不能通过的。

这让他回忆起了在不知道多久之前躲避一匹马的追击的英勇故事。

于是，他从这个棋盘的左上角开始，尝试只能向右或向下走有多少种能够到达右下角的方案。

最后，他走出了 $L$ 种方案。

但是他忘记了棋盘的样子，只是依稀记得 $n\le 30$。

于是他找到了很久之前帮助他判断是他赢还是红方帅赢的你。

希望你能够给出一组构造，使得从左上角到右下角的方案数为 $L$。

保证 $L$ 在范围内均匀随机生成。

Input Format

本题多测。

第一行，一个正整数 $T$，表示数据组数。

随后输入 $T$ 组数据。对于每组数据，输入一个非负整数 $L$。

Output Format

对于每组数据，第一行输出一个正整数 $n$，表示棋盘的大小，如果无解，请输出 $-1$。

如果有解，接下来的 $n$ 行，每行 $n$ 个 $0$ 或者 $1$，分别表示这个格子不可以或可以通过。

请保证左上角与右下角的格子可以通过。

2
2
20

3
1 1 1
1 0 1
1 1 1
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

Hint

评分标准

对于某一个测试点，若你的输出有无解均判断正确，则你至少可以获得 $20\%$ 的分数。

特别的，如果你的输出的格式不合法，你可能会获得 $0$ 分，一种格式合法的输出是全 $1$ 棋盘。

数据范围

本题共包含 $20$ 个测试点，每个测试点 $5$ 分。

对于测试点 $1\sim 5$，满足 $L\le 5i$，其中 $i$ 表示测试点编号。

对于测试点 $6\sim 20$，满足 $L\le 10^{i-4}$，其中 $i$ 表示测试点编号。

对于所有数据，保证 $T=100$，$0\le L\le 10^{16}$，$L$ 在范围内均匀随机生成。

你需要保证你给出的 $n$ 满足 $1\le n\le 30$。