题目描述

给定一个长度为 $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$ 是最终得到的字符串。

4
3
012
4
0145
5
00000
11
98765432101

Case #1: 22
Case #2: 26
Case #3: 00000
Case #4: 1

提示

在样例 #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 完成