Roaring Years
시간 제한30초메모리 제한1024 MB
주어진 연도 Y에 대해, 십진 표기를 두 개 이상의 서로 다른 연속한 양의 정수를 증가하는 순서로 이어 붙인 수로 나타낼 수 있는 Y보다 큰 가장 작은 연도를 구한다.
문제
2021년에는 100년 넘게 일어나지 않았던 일이 일어난다. 2021은 1920처럼 roaring year이다. 양의 정수 y로 표현되는 연도가 roaring year라는 것은, y의 십진 표기(앞의 0 없이)가 두 개 이상의 서로 다른 연속한 양의 정수의 십진 표기(앞의 0 없이)를 오름차순으로 이어 붙인 것이 될 때를 말한다. 이때 2021은 20과 21을 이어 붙인 것이므로 roaring year이다.
roaring year의 달력 세 장. 각 연도가 얼마나 roaring한지 표시되어 있다.
다른 roaring year의 예로는 12, 789, 910, 1234, 9899100이 있다. 2020은 roaring year가 아니었다. 2020으로 이어 붙여지는 두 개 이상의 양의 정수 목록은 [20,20]뿐인데, 이는 연속한 정수로 이루어지지 않기 때문이다. 마찬가지로 2019에 대해서는 [20,1,9], [201,9], [20,19] 세 목록만 있다. 앞의 두 개는 연속한 정수로 이루어지지 않고, 세 번째는 정수가 오름차순이 아니다. 따라서 2019도 roaring year가 아니었다. 마지막 예로, 778은 roaring year가 아니었는데 [7,78]과 [77,8]은 연속한 정수로 이루어지지 않고 [7,7,8]은 서로 다른 정수로 이루어지지 않기 때문이다.
현재 연도(roaring year일 수도 있고 아닐 수도 있다)가 주어질 때, 다음 roaring year가 무엇인지 구하라.
입력
입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 그다음 T개의 줄이 이어지며, 각 줄은 테스트 케이스 하나를 나타내고 정수 Y 하나를 포함한다. Y는 현재 연도이다.
출력
각 테스트 케이스마다 Case #x: z를 한 줄에 출력한다. x는 테스트 케이스 번호(1부터 시작)이고, z는 Y보다 엄격히 큰 첫 번째 roaring year이다.
제한
- 1 ≤ T ≤ 100.
힌트
마지막 샘플 케이스에서 102는 roaring year가 아니다. [10,2]는 연속한 정수의 목록이 아니며, [1,02]를 쓰기 위해 2를 앞에 0을 붙여 쓸 수는 없기 때문이다.