P16867 [GKS 2021 #H] Silly Substitutions

给定一个长度为 $N$ 的字符串 $S$，由数字 $0$-$9$ 组成。按以下顺序对字符串执行操作： 1. 找出所有子串 $\mathtt{01}$，并将其替换为 $\mathtt{2}$。 2. 找出所有子串 $\mathtt{12}$，并将其替换为 $\mathtt{3}$。 3. 找出所有子串 $\mathtt{23}$，并将其替换为 $\mathtt{4}$。 4. 找出所有子串 $\mathtt{34}$，并将其替换为 $\mathtt{5}$。 5. 找出所有子串 $\mathtt{45}$，并将其替换为 $\mathtt{6}$。 6. 找出所有子串 $\mathtt{56}$，并将其替换为 $\mathtt{7}$。 7. 找出所有子串 $\mathtt{67}$，并将其替换为 $\mathtt{8}$。 8. 找出所有子串 $\mathtt{78}$，并将其替换为 $\mathtt{9}$。 9. 找出所有子串 $\mathtt{89}$，并将其替换为 $\mathtt{0}$。 10. 找出所有子串 $\mathtt{90}$，并将其替换为 $\mathtt{1}$。 重复这一过程（按照相同的顺序），直到上述操作不再改变字符串。例如，若 $S$ 为 $\mathtt{12}$，则操作 $1$ 不会影响字符串，但操作 $2$ 会将字符串变为 $\mathtt{3}$。可以验证，无论重复多少次上述过程，字符串都不会再改变。 对于给定的 $S$，你的任务是求出最终的字符串。

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例由两行组成。 每个测试用例的第一行包含一个整数 $N$，表示字符串 $S$ 的长度。 每个测试用例的第二行包含一个长度为 $N$ 的字符串 $S$。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是最终得到的字符串。

在样例 #1 中，子串 $\mathtt{01}$ 被替换为 $\mathtt{2}$，得到字符串 $\mathtt{22}$，后续操作不会再改变它。因此最终字符串为 $\mathtt{22}$。 在样例 #2 中，子串 $\mathtt{01}$ 被替换为 $\mathtt{2}$，得到字符串 $\mathtt{245}$。然后子串 $\mathtt{45}$ 被替换为 $\mathtt{6}$，得到字符串 $\mathtt{26}$，不再受任何操作影响。因此最终字符串为 $\mathtt{26}$。 在样例 #3 中，无法对给定字符串执行任何操作，因此字符串保持不变。 在样例 #4 中，所有操作可以顺序作用于字符串，最终得到字符串 $\mathtt{1}$。 ### 限制条件 $1 \le T \le 100$。 输入字符串仅由数字 $0$-$9$ 组成。 **测试集 1** $1 \le N \le 100$。 **测试集 2** 最多 $10$ 个测试用例满足： $1 \le N \le 5 \times 10^5$。 其余测试用例满足： $1 \le N \le 100$。 翻译由 DeepSeek V4 Pro 完成