도전 9

Ada는 John에게 양의 정수 $\mathbf{N}$을 준다. 그녀는 주어진 수 $\mathbf{N}$의 아무 위치에나 정확히 하나의 숫자(0 $\dots$ 9)를 삽입하여, 앞에 0이 없고 $9$의 배수인 새로운 수를 만들라고 한다. $\mathbf{N}$에는 앞에 0이 없음이 보장된다.

John은 작은 수를 선호하므로, 가능한 수 중 가장 작은 수를 만들고 싶어 한다. John을 도와줄 수 있는가?

제한

메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$.

테스트 세트 1

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

테스트 세트 2

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

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

각 테스트 케이스는 Ada가 John에게 주는 수인 양의 정수 $\mathbf{N}$을 포함하는 한 줄로 이루어진다.

각 테스트 케이스마다 Case #$x$: $y$을 포함하는 한 줄을 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 John이 만든 새로운 수이다. 앞서 언급했듯이 $y$에는 앞에 0이 올 수 없다.

샘플 케이스 #1에서 나눗셈 조건을 만족하도록 만들 수 있는 수는 $45$과 $54$뿐이다. John은 더 작은 수를 선택한다.

샘플 케이스 #2에서는 $333$만 가능하다.

샘플 케이스 #3에는 가능한 선택지가 $212121$, $122121$, $121221$, $121212$의 네 가지이며, 그중 가장 작은 수는 $121212$이다.