Description

Jamcoin 是一种长度为 $\mathrm{N}$（$\mathrm{N} \geqslant 2$）的二进制串，满足以下条件：

• 每一位都是 $0$ 或 $1$。
• 首位为 $1$，末位也为 $1$。
• 无论将该串按 $2$ 到 $10$ 进制中的哪一种解释，所得的数都不是质数。

并非所有由 $0$ 和 $1$ 组成的串都是 jamcoin。例如，$101$ 不是 jamcoin，因为它在 $2$ 进制下的数值是 $5$，而 $5$ 是质数。但 $1001$ 是 jamcoin：在 $2$ 到 $10$ 进制下分别对应 $9, 28, 65, 126, 217, 344, 513, 730, 1001$，其中每一个都不是质数。

据说有些社区会用 jamcoin 作为货币。当你把 jamcoin 发送给别人时，礼貌的做法是为每个进制（$2$ 到 $10$）下 jamcoin 的数值都提供一个非平凡因子，以证明该 jamcoin 的合法性。（对于正整数 $K$，非平凡因子是指除了 $1$ 和 $K$ 之外的正整数因子。）为方便起见，这些因子需用 $10$ 进制表示。

例如，前述 jamcoin $1001$，对于 $2$ 到 $10$ 进制的解释，可以选择的非平凡因子分别为：$3, 7, 5, 6, 31, 8, 27, 5, 77$。

你能否生成 $\mathrm{N}$ 位、互不相同的 $\mathrm{J}$ 个 jamcoin，并且为每个 jamcoin 提供一组合法性证明？

Input Format

输入的第一行是测试用例数量 $\mathrm{T}$。接下来有 $\mathrm{T}$ 组测试用例，每组一行，包含两个整数 $\mathrm{N}$ 和 $\mathrm{J}$。

Output Format

对于每组测试用例，输出 $\mathrm{J}+1$ 行。第一行只包含 Case #x:，其中 $x$ 是测试用例编号（从 $1$ 开始）。接下来的 $\mathrm{J}$ 行，每行包含一个长度为 $\mathrm{N}$ 的 jamcoin，后跟九个整数，第 $i$ 个整数（$i$ 从 $1$ 开始）为该 jamcoin 在 $i+1$ 进制下的一个非平凡因子。

所有 jamcoin 必须互不相同。即使因子组不同，也不能输出相同的 jamcoin。

1
6 3

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

Hint

在样例中，为了便于说明，$\mathrm{N}$ 和 $\mathrm{J}$ 取了很小的值。注意，这组样例不会出现在 Small 或 Large 数据集中。

这只是众多合法解中的一种。你也可以用其他 jamcoin 及其因子组。补充说明：

• $110111$ 不能作为输出，因为它在 $3$ 进制下为 $337$，而 $337$ 是质数。
• $010101$ 虽然 $10101$ 是 jamcoin，但不能作为输出，因为 jamcoin 必须以 $1$ 开头。
• $101010$ 也不能作为输出，因为 jamcoin 必须以 $1$ 结尾。
• $110011$ 也是 jamcoin，可以出现在输出中，但由于输出必须恰好有 $\mathrm{J}$ 个 jamcoin，不能再多输出。
• 对于样例输出的第一个 jamcoin，后面的第一个数不能是 $1$ 或 $35$，因为这两者是 $35$（$100011$ 在 $2$ 进制下）的平凡因子。

限制条件

• $T = 1$。（只有一组测试数据。）
• 保证存在至少 $J$ 个不同的长度为 $N$ 的 jamcoin。

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

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

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

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

注意，这道题不同于一般的 Code Jam 题目，你已经提前知道每个输入文件的内容。例如，小数据集的输入文件永远如下：

1
16 50

因此，你可以在真正下载输入文件和开始计时之前，提前做一些计算。

翻译由 GPT4.1 完成。