정돈된 수 (Large)
시간 제한5초메모리 제한512 MB
N이 10^18 이하로 주어질 때, N을 넘지 않으면서 십진수 각 자리가 감소하지 않는 가장 큰 수를 구한다.
문제
타티아나는 무엇이든 가지런히 두는 것을 좋아한다. 장난감은 작은 것부터 큰 것 순서로, 연필은 짧은 것부터 긴 것 순서로, 컴퓨터는 오래된 것부터 새것 순서로 놓는다. 어느 날 수 세기를 연습하다가, 앞에 0을 붙이지 않고 10진법으로 적었을 때 각 자리 숫자가 감소하지 않는 순서로 놓이는 정수가 있다는 사실을 알아차렸다. 8, 123, 555, 224488이 그런 수다. 타티아나는 이런 수를 정돈된 수라고 부르기로 했다. 20, 321, 495, 999990처럼 이 성질을 만족하지 않는 수는 정돈된 수가 아니다.
타티아나는 방금 1부터 까지 모든 양의 정수를 오름차순으로 셌다. 타티아나가 센 마지막 정돈된 수는 무엇인가?
입력
첫째 줄에 테스트 케이스의 개수 가 주어진다. 이어서 개의 줄이 주어진다. 각 줄에는 타티아나가 마지막으로 센 수 이 정수 하나로 주어진다.
제한
출력
각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. 는 1부터 시작하는 테스트 케이스 번호이고, 는 타티아나가 센 마지막 정돈된 수다.