정돈된 수 (Small)

타티아나는 무엇이든 순서대로 정리한다. 장난감은 작은 것부터 큰 것까지, 연필은 짧은 것부터 긴 것까지, 컴퓨터는 오래된 것부터 최신 것까지 늘어놓는다. 어느 날 수를 세다가, 앞자리에 0이 없는 10진수 중에 자릿수가 넓은 의미로 증가하는 순서, 즉 각 자리 숫자가 바로 다음 자리 숫자보다 크지 않은 수가 있다는 사실을 알아차렸다. 8, 123, 555, 224488이 그런 수다. 타티아나는 이런 수를 정돈된 수라고 부르기로 했다. 20, 321, 495, 999990처럼 이 성질을 만족하지 않는 수는 정돈된 수가 아니다.

타티아나는 1부터 $N$까지 모든 양의 정수를 오름차순으로 세었다. 세는 동안 마지막으로 나온 정돈된 수를 구하라. 다시 말해 $N$ 이하인 정돈된 수 중 가장 큰 수를 구하면 된다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어지는 $T$개의 줄에 각 테스트 케이스가 하나씩 주어지며, 각 줄에는 타티아나가 마지막으로 센 수 $N$이 정수로 주어진다.

• $1 \le T \le 100$
• $1 \le N \le 10^{18}$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 그 테스트 케이스에서 마지막으로 센 정돈된 수다.