정돈된 수 (Large)

타티아나는 무엇이든 가지런히 두는 것을 좋아한다. 장난감은 작은 것부터 큰 것 순서로, 연필은 짧은 것부터 긴 것 순서로, 컴퓨터는 오래된 것부터 새것 순서로 놓는다. 어느 날 수 세기를 연습하다가, 앞에 0을 붙이지 않고 10진법으로 적었을 때 각 자리 숫자가 감소하지 않는 순서로 놓이는 정수가 있다는 사실을 알아차렸다. 8, 123, 555, 224488이 그런 수다. 타티아나는 이런 수를 정돈된 수라고 부르기로 했다. 20, 321, 495, 999990처럼 이 성질을 만족하지 않는 수는 정돈된 수가 아니다.

타티아나는 방금 1부터 $N$까지 모든 양의 정수를 오름차순으로 셌다. 타티아나가 센 마지막 정돈된 수는 무엇인가?

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

제한

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

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