엉뚱한 치환

숫자 0-9로 이루어진 길이 $\mathbf{N}$의 문자열 $\mathbf{S}$가 주어진다. 문자열에 다음 연산들을 주어진 순서대로 수행한다.

• 모든 부분 문자열 01을 찾아 각각을 2로 바꾼다.

• 모든 부분 문자열 12을 찾아 각각을 3로 바꾼다.

• 모든 부분 문자열 23을 찾아 각각을 4로 바꾼다.

• 모든 부분 문자열 34을 찾아 각각을 5로 바꾼다.

. . .

• 모든 부분 문자열 89을 찾아 각각을 0로 바꾼다.

• 모든 부분 문자열 90을 찾아 각각을 1로 바꾼다.

위 연산 중 어느 것도 문자열을 바꾸지 않을 때까지 이 과정을 주어진 동일한 순서로 반복한다. 예를 들어 $\mathbf{S}$가 12라면, 연산 $1$이 문자열에 영향을 주지 않더라도 그 연산에서 멈추지 않고 연산 $2$을 수행하여 문자열을 3로 바꾼다. 그 후에는 위 과정을 몇 번 반복하더라도 문자열이 더 이상 바뀌지 않음을 알 수 있다.

주어진 $\mathbf{S}$에 대한 최종 문자열이 어떤 모습인지 구하는 것이 과제이다.

제한

메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. 입력 문자열은 숫자 0-9로만 이루어진다.

테스트 세트 1

시간 제한: 20초. $1 \le \mathbf{N} \le 100$.

테스트 세트 2

시간 제한: 60초. 최대 10개의 케이스에 대해: $1 \le \mathbf{N} \le 5 \times 10^5$. 나머지 케이스에 대해: $1 \le \mathbf{N} \le 100$.

입력의 첫 번째 줄에 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다.

각 테스트 케이스의 첫 번째 줄에는 문자열 $\mathbf{S}$의 길이를 나타내는 정수 $\mathbf{N}$이 주어진다.

각 테스트 케이스의 두 번째 줄에는 길이 $\mathbf{N}$의 문자열 $\mathbf{S}$이 주어진다.

각 테스트 케이스마다 Case #$x$: $y$을 포함하는 한 줄을 출력한다. 여기서 $x$은 (1부터 시작하는) 테스트 케이스 번호이고, $y$은 얻어진 최종 문자열이다.

예제 케이스 #1에서는 부분 문자열 01을 2로 바꾸며, 그 결과인 문자열 22은 어떤 연산에도 더 이상 영향을 받지 않는다. 따라서 최종 문자열은 22이다.

예제 케이스 #2에서는 부분 문자열 01을 2로 바꾸며, 그 결과인 문자열은 245이다. 부분 문자열 45을 6로 바꾸며, 그 결과인 문자열 26은 어떤 연산에도 더 이상 영향을 받지 않는다. 따라서 최종 문자열은 26이다.

예제 케이스 #3에서는 주어진 문자열에 연산을 수행할 수 없으므로 문자열이 바뀌지 않는다.

예제 케이스 #4에서는 모든 연산을 문자열에 차례대로 수행할 수 있으며, 최종 문자열은 1이다.