P16867 [GKS 2021 #H] Silly Substitutions

You are given a string $S$ of length $N$ which consists of digits $0$-$9$. You do the following operations on the string in the order given. 1. Find all the substrings $\mathtt{01}$ and replace each of them with $\mathtt{2}$. 2. Find all the substrings $\mathtt{12}$ and replace each of them with $\mathtt{3}$. 3. Find all the substrings $\mathtt{23}$ and replace each of them with $\mathtt{4}$. 4. Find all the substrings $\mathtt{34}$ and replace each of them with $\mathtt{5}$. 5. Find all the substrings $\mathtt{45}$ and replace each of them with $\mathtt{6}$. 6. Find all the substrings $\mathtt{56}$ and replace each of them with $\mathtt{7}$. 7. Find all the substrings $\mathtt{67}$ and replace each of them with $\mathtt{8}$. 8. Find all the substrings $\mathtt{78}$ and replace each of them with $\mathtt{9}$. 9. Find all the substrings $\mathtt{89}$ and replace each of them with $\mathtt{0}$. 10. Find all the substrings $\mathtt{90}$ and replace each of them with $\mathtt{1}$. You repeat this process in the same given order until none of the above operations change the string. For example, if $S$ is $\mathtt{12}$ then we do not stop at operation $1$ since it does not affect the string but perform operation $2$ and change the string to $\mathtt{3}$. We can see that the string does not change further no matter how many times we repeat the above process. Your task is to find how the final string will look like for the given $S$.

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case consists of two lines. The first line of each test case contains an integer $N$, denoting the length of the string $S$. The second line of each test case contains a string $S$ of length $N$.

For each test case, output one line containing Case #$x$: $y$, where $x$ is the test case number (starting from $1$) and $y$ is the final string obtained.

In Sample Case #$1$, substring $01$ is replaced with $2$ and the resulting string is $22$ which is not affected further by any of the operations. Therefore final string is $22$. In Sample Case #$2$, substring $01$ is replaced with $2$ and the resulting string is $245$. The substring $45$ is replaced with $6$ and the resulting string is $26$ which is not further affected by any of the operations. Therefore final string is $26$. In Sample Case #$3$, since the operations cannot be performed on the given string, the string does not change. In Sample Case #$4$, all the operations can be performed sequentially on the string and the final string is $1$. ### Limits $1 \le T \le 100$. The input string only consists of digits $0$-$9$. **Test Set $1$** $1 \le N \le 100$. **Test Set $2$** For at most $10$ cases: $1 \le N \le 5 \times 10^5$. For the remaining cases: $1 \le N \le 100$.