Description

注意：每当题目描述中提到"随机选择"时，均表示"在所有有效可能性中均匀随机且独立地选择"。

Banana Rocks 公司开发了一款基于云计算的优质随机数生成服务，旨在成为随机性领域的新黄金标准。

最初的设计是：一组服务器接收一个最多包含 $\mathbf{U}$ 位十进制数字的正整数 $\mathbf{M}$ 作为请求，然后返回一个在 1 到 $\mathbf{M}$ 之间（含端点）随机选择的整数。然而，这些服务器被"过度随机化"了——它们没有使用常规的 0-9 数字输出结果，而是每个服务器都随机选取了 10 个不同的大写英文字母作为数字，并随机将这些字母映射到 0-9 的唯一值。

当前情况的正式描述如下：

• 每个服务器有一个由恰好 10 个不同大写字母组成的数字字符串 $\mathbf{D}$
• 该字符串定义了字母与十进制数字的映射关系：$\mathbf{D}$ 中从左数第 $j$ 个字符（从 0 开始计数）代表数值为 $j$ 的数字
• 例如，若 $\mathbf{D}$ 为 CODEJAMFUN，则 C 代表数字 0，O 代表数字 1，N 代表数字 9。数字 379009 将被编码为 EFNCCN

当服务器收到第 $i$ 个参数为 $M_i$ 的查询时，会：

1. 从 1 到 $M_i$ 的范围内随机选择一个整数 $N_i$
2. 使用 $\mathbf{D}$ 中的字母数字表示法将其转换为无前导零的十进制字符串
3. 返回结果字符串 $R_i$ 作为响应

我们收集了一些数据，认为可以用来恢复每个服务器的秘密数字字符串 $\mathbf{D}$。我们向每个服务器发送了 $10^4$ 次查询：

• 每次查询的 $M_i$ 是从 1 到 $10^{\mathbf{U}}-1$ 范围内随机选择的
• 收到的响应 $R_i$ 是一个最多包含 $\mathbf{U}$ 个大写字母的字符串
• 我们记录了这些 $(M_i, R_i)$ 对

但在将这些记录转移到新存储设备时，部分服务器记录中的所有 $M_i$ 整数值都损坏无法读取了。你能帮我们找出每个服务器的数字字符串 $\mathbf{D}$ 吗？

Input Format

输入第一行包含测试用例数量 $\mathbf{T}$。随后是 $\mathbf{T}$ 个测试用例，每个用例包含一个服务器的记录：

• 第一行是整数 $\mathbf{U}$，表示查询参数 $M_i$ 的选择范围上限为 $10^{\mathbf{U}}-1$
• 接下来是恰好 $10^4$ 行，每行包含一个十进制整数 $\mathbf{Q}_i$ 和字符串 $\mathbf{R}_i$
  • 若 $\mathbf{Q}_i = -1$，表示该次查询的 $M_i$ 未知
  • 否则 $\mathbf{Q}_i = M_i$

Output Format

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是该服务器对应的数字字符串 $\mathbf{D}$。

Hint

数据范围

• $1 \leqslant \mathbf{T} \leqslant 10$
• $\mathbf{D}$ 是恰好 10 个不同大写字母组成的字符串，从所有可能组合中独立均匀随机选取
• 对所有 $i$，$M_i$ 从 1 到 $10^{\mathbf{U}}-1$ 范围内独立均匀随机选取
• 对所有 $i$，$N_i$ 从 1 到 $M_i$ 范围内独立均匀随机选取
• 对所有 $i$，$R_i$ 是 $N_i$ 的十进制表示，使用 $\mathbf{D}$ 中第 $j$ 个字母代表数字 $j$

测试集 1（9 分，可见判定）

• 对所有 $i$，$\mathbf{Q}_i = M_i$
• $\mathbf{U} = 2$

测试集 2（10 分，可见判定）

• 对所有 $i$，$\mathbf{Q}_i = M_i$
• $\mathbf{U} = 16$

测试集 3（17 分，可见判定）

• 对所有 $i$，$\mathbf{Q}_i = -1$
• $\mathbf{U} = 16$

翻译由 DeepSeek V3 完成