챌린지 나인

아다는 존에게 양의 정수 $N$을 준다. 그녀는 존에게 주어진 수 $N$의 어느 자리에든 숫자(0부터 9까지) 정확히 하나를 끼워 넣어서, 9의 배수이면서 앞자리가 0이 아닌 새로운 수를 만들라고 도전한다. $N$은 앞자리가 0으로 시작하지 않는다고 보장된다.

존은 작은 수를 선호하므로, 그런 수 중에서 가장 작은 수를 만들고 싶어 한다. 존을 도와주자.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다.

각 테스트 케이스는 아다가 존에게 준 양의 정수 $N$이 한 줄에 주어진다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 존이 만든 새로운 수다. $y$는 앞자리가 0이 될 수 없다.

• $1 \le T \le 100$.

예시 1에서는 9의 배수 조건을 만족하는 수가 $45$와 $54$ 두 개뿐이다. 존은 더 작은 $45$를 고른다.

예시 2에서는 가능한 수가 $333$ 하나뿐이다.

예시 3에서는 $212121$, $122121$, $121221$, $121212$ 네 가지 경우가 있고, 그중 가장 작은 수는 $121212$다.