단정한 수

Tatiana는 물건을 단정하게 정리하는 것을 좋아한다. 그녀의 장난감은 가장 작은 것부터 가장 큰 것까지, 연필은 가장 짧은 것부터 가장 긴 것까지, 컴퓨터는 가장 오래된 것부터 가장 최신인 것까지 정렬되어 있다. 어느 날 수 세기를 연습하던 중, 일부 정수는 선행 영 없이 10진법으로 썼을 때 그 자릿수들이 비감소 순서로 정렬되어 있다는 것을 알아차렸다. 그 예로는 8, 123, 555, 224488가 있다. 그녀는 이러한 수를 단정한 수라고 부르기로 했다. 20, 321, 495, 999990처럼 이 성질을 갖지 않는 수는 단정한 수가 아니다.

그녀는 방금 1부터 N까지의 모든 양의 정수를 오름차순으로 세었다. 그녀가 센 마지막 단정한 수는 무엇이었는가?

제한

시간 제한: 테스트 세트당 20초. 메모리 제한: 1 GB. 1 ≤ T ≤ 100.

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ N ≤ 1000.

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ N ≤ $10^{18}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 줄이 주어진다. 각 줄은 Tatiana가 마지막으로 센 수인 정수 N 하나로 테스트 케이스를 설명한다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 테스트 케이스 번호이며(1부터 시작), y은 Tatiana가 센 마지막 단정한 수이다.

마지막 예제 케이스는 작은 데이터 세트에 출제되지 않는다는 점에 유의하라.