Description

在 Code Jam 团队中，我们喜欢互相发送全字母短语（pangram），即包含英语字母表中每个字母至少一次的短语。一个常见的例子是 “the quick brown fox jumps over the lazy dog”。有时我们的全字母短语中包含机密信息，例如 CJ QUIZ: KNOW BEVY OF DP FLUX ALGORITHMS，因此我们需要保证它们的安全。

我们翻看了一本密码学教材几分钟，了解到分解两个大质数的乘积非常困难，于是我们基于这个事实设计了一种加密方案。首先，我们做了一些准备：

• 我们选择了 $26$ 个不同的质数，且每个质数都不大于某个整数 $N$。
• 我们将这些质数按升序排列。然后，将最小的质数分配给字母 $A$，第二小的分配给 $B$，以此类推。
• 团队中的每个人都记住了这份列表。

现在，每当我们想要发送一个全字母短语作为消息时，我们首先去除所有空格，形成明文消息。然后，我们记录下明文第一个字母对应的质数与第二个字母对应的质数的乘积。接着，记录第二个和第三个字母对应质数的乘积，依此类推，直到倒数第二个和最后一个字母对应质数的乘积。这个新的数值列表就是我们的密文。密文中的数值个数比明文字符数少 $1$。

例如，假设 $N = 103$，我们选择了前 $26$ 个奇质数，因为我们担心偶数太容易分解。那么 $A = 3$，$B = 5$，$C = 7$，$D = 11$，以此类推，直到 $Z = 103$。又假设我们想加密上面的全字母短语 CJ QUIZ KNOW BEVY OF DP FLUX ALGORITHMS，那么明文为 CJQUIZKNOWBEVYOFDPFLUXALGORITHMS。此时密文的第一个数值是 $7$（C 对应的质数）乘以 $31$（J 对应的质数）$= 217$；下一个数值是 $1891$，以此类推，最后一个数值是 $3053$。

我们会给你一个密文消息和我们使用的 $N$ 的值。我们不会告诉你用的是哪些质数，也不会告诉你如何解密密文。你能否恢复出明文呢？

Input Format

输入的第一行包含测试用例的数量 $T$。接下来有 $T$ 组测试用例，每组测试用例包含两行。第一行包含两个整数：$N$（如上所述）和 $L$，即密文数值列表的长度。第二行包含 $L$ 个整数，表示密文数值列表。

Output Format

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是由 $L+1$ 个大写英文字母组成的明文字符串。

2
103 31
217 1891 4819 2291 2987 3811 1739 2491 4717 445 65 1079 8383 5353 901 187 649 1003 697 3239 7663 291 123 779 1007 3551 1943 2117 1679 989 3053
10000 25
3292937 175597 18779 50429 375469 1651121 2102 3722 2376497 611683 489059 2328901 3150061 829981 421301 76409 38477 291931 730241 959821 1664197 3057407 4267589 4729181 5335543

Case #1: CJQUIZKNOWBEVYOFDPFLUXALGORITHMS
Case #2: SUBDERMATOGLYPHICFJKNQVWXZ

Hint

限制条件

• $1 \leq T \leq 100$。
• $25 \leq L \leq 100$。
• 明文包含每个英文字母至少一次。

测试点 1（10 分，可见）

• $101 \leq N \leq 10000$。

测试点 2（15 分，隐藏）

• $101 \leq N \leq 10^{100}$。

由 ChatGPT 4.1 翻译