Jamcoin 是一个长度为 $N \ge 2$ 的字符串，具有以下属性：

• 每一位数字要么是 0，要么是 1。
• 第一位数字是 1，最后一位数字是 1。
• 如果将该字符串在 2 到 10 之间的任意进制下进行解释，得到的数值都不是素数。

并非所有的 0 和 1 组成的字符串都是 jamcoin。例如，101 不是 jamcoin；它在 2 进制下的解释是 5，这是一个素数。但字符串 1001 是一个 jamcoin：在 2 到 10 进制下，它的解释分别为 9、28、65、126、217、344、513、730 和 1001，其中没有一个是素数。

我们听说有些社区使用 jamcoin 作为一种货币。在向某人发送 jamcoin 时，礼貌的做法是证明该 jamcoin 是合法的，方法是提供该 jamcoin 在 2 到 10 进制下解释的非平凡约数。（正整数 $K$ 的非平凡约数是指除了 1 或 $K$ 之外，能整除 $K$ 的某个正整数。）为方便起见，这些约数必须以 10 进制表示。

例如，对于上述 jamcoin 1001，一组可能的 2 到 10 进制下的非平凡约数分别为：3、7、5、6、31、8、27、5 和 77。

你能生成 $J$ 个不同的长度为 $N$ 的 jamcoin，并附上它们合法的证明吗？

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例；每个测试用例由一行组成，包含两个整数 $N$ 和 $J$。

输出格式

对于每个测试用例，输出 $J+1$ 行。第一行必须仅包含 Case #x:，其中 $x$ 是测试用例编号（从 1 开始）。最后 $J$ 行中的每一行必须包含一个长度为 $N$ 的 jamcoin，后跟九个整数。这九个整数中的第 $i$ 个（从 1 开始计数）必须是该 jamcoin 在 $i+1$ 进制下解释后的一个非平凡约数。

所有这些 jamcoin 必须各不相同。你不能在两行中提交同一个 jamcoin，即使你每次使用不同的约数集合也不行。

数据范围

时间限制：5 秒。 内存限制：1 GB。 $T = 1$。（只有一个测试用例。） 保证至少存在 $J$ 个长度为 $N$ 的不同 jamcoin。

小数据集（测试集 1 - 可见；10 分）

$N = 16$。 $J = 50$。

大数据集（测试集 2 - 隐藏；20 分）

$N = 32$。 $J = 500$。

请注意，与 Code Jam 的常规问题不同，你已经知道了每个输入文件的确切内容。例如，小数据集的输入文件将始终恰好是这两行：

1

16 50

因此，你可以在下载输入文件并开始计时之前进行一些计算。

样例

样例输入 1

1
6 3

样例输出 1

Case #1:
100011 5 13 147 31 43 1121 73 77 629
111111 21 26 105 1302 217 1032 513 13286 10101
111001 3 88 5 1938 7 208 3 20 11

在此样例中，为了便于解释，我们使用了非常小的 $N$ 和 $J$ 值。请注意，此样例不会出现在小数据集或大数据集中。

这只是多个有效解中的一个。可以使用其他 jamcoin 集合，并且存在许多其他可能的 10 进制非平凡约数集合。一些说明：

• 110111 不能包含在输出中，因为例如，它在 3 进制下解释为 337（$1 \times 243 + 1 \times 81 + 0 \times 27 + 1 \times 9 + 1 \times 3 + 1 \times 1$），而 337 是素数。
• 010101 不能包含在输出中，即使 10101 是一个 jamcoin，因为 jamcoin 必须以 1 开头。
• 101010 不能包含在输出中，因为 jamcoin 必须以 1 结尾。
• 110011 是另一个可以用于输出的 jamcoin，但不能添加到此输出的末尾，因为输出必须恰好包含 $J$ 个示例。
• 对于样例输出中的第一个 jamcoin，100011 之后的第一个数字不能是 1 或 35，因为它们是 35（100011 在 2 进制下的值）的平凡约数。