P14952 过河卒

> > 这可能是我出题生涯出过最好的题了 > 这可能是我出题生涯出过最烂的题了

一个几年前刚刚和两个红方帅对抗完的黑卒正在二维平面上闲逛。 这时，他看见了一个 $n$ 行 $n$ 列的棋盘。 这个棋盘的某些格子是可以通过的，有些是不能通过的。 这让他回忆起了在不知道多久之前躲避一匹马的追击的英勇故事。 于是，他从这个棋盘的左上角开始，尝试只能向右或向下走有多少种能够到达右下角的方案。 最后，他走出了 $L$ 种方案。 但是他忘记了棋盘的样子，只是依稀记得 $n\le 30$。 于是他找到了很久之前帮助他判断是他赢还是红方帅赢的你。 希望你能够给出一组构造，使得从左上角到右下角的方案数为 $L$。 **保证 $L$ 在范围内均匀随机生成。**

**本题多测。** 第一行，一个正整数 $T$，表示数据组数。 随后输入 $T$ 组数据。对于每组数据，输入一个非负整数 $L$。

对于每组数据，第一行输出一个正整数 $n$，表示棋盘的大小，如果无解，请输出 $-1$。 如果有解，接下来的 $n$ 行，每行 $n$ 个 $0$ 或者 $1$，分别表示这个格子不可以或可以通过。 **请保证左上角与右下角的格子可以通过。**

### 评分标准 对于某一个测试点，若你的输出有无解均判断正确，则你至少可以获得 $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$。**