一个包含 $N$ 个节点的无向图的生成树（spanning tree）是指一个包含 $N-1$ 条边，且仅使用原图中的边并覆盖所有 $N$ 个节点的树。

请构造一个节点数至少为 2、至多为 22 的图，使得该图恰好有 $K$ 种不同的生成树。（若两棵生成树所包含的边集不同，则认为它们是不同的。）该图在任意两个节点之间至多只能有一条边，且不能包含自环（即连接节点与其自身的边）。

题目保证对于下述范围内的每一个 $K$，至少存在一个满足条件的图。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来有 $T$ 行，每行包含一个整数 $K$，表示所需的生成树数量。

输出格式

对于每个测试用例，首先输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是你构造的图的节点数（$2 \le y \le 22$）。接着输出 $y$ 行，每行包含 $y$ 个字符，表示图的邻接矩阵。第 $i$ 行的第 $j$ 个字符应为 1（如果第 $i$ 个节点和第 $j$ 个节点之间有边）或 0（否则）。注意，该矩阵必须是对称的，且主对角线上的元素全为 0。

如果存在多种答案，你可以输出其中任意一个。

数据范围

时间限制：120 秒。 内存限制：1 GB。 $1 \le T \le 300$。 $3 \le K \le 10000$。

样例

输入 1

2
3
8

输出 1

Case #1: 3
011
101
110
Case #2: 4
0111
1001
1001
1110

说明

在样例 1 中，该图是一个三角形，移除任意一条边都会产生一棵不同的生成树。

在样例 2 中，我们解法中的可用边为 1-2, 1-3, 1-4, 2-4 和 3-4。这八种不同的生成树由以下边集定义： 1-2, 1-3, 1-4 1-2, 1-3, 2-4 1-2, 1-3, 3-4 1-2, 1-4, 3-4 1-2, 2-4, 3-4 1-3, 1-4, 2-4 1-3, 2-4, 3-4 1-4, 2-4, 3-4