다음 수

당신은 수의 목록을 적고 있다. 이 목록에는 1 이상 9 이하의 각 i에 대해, 십진수 표현에서 i와 같은 숫자가 정확히 $D_{i}$개인 모든 수가 포함된다. 당신은 이 수들을 오름차순으로 적고 있다.

예를 들어, '1'가 두 개이고 '5'가 하나인 모든 수를 적고 있을 수 있다. 목록은 115, 151, 511, 1015, 1051로 시작할 것이다.

마지막으로 적은 수 N이 주어질 때, 목록의 다음 수를 구한다.

제한

메모리 제한: 1 GB.

소형 데이터 세트

시간 제한: 20초. 1 ≤ T ≤ 50 1 ≤ N ≤ $10^{6}$

대형 데이터 세트

시간 제한: 30초. 1 ≤ T ≤ 500 1 ≤ N ≤ $10^{20}$

입력의 첫 줄에는 테스트 케이스의 수를 나타내는 정수 T가 주어진다. 이어지는 T개의 줄에는 각 테스트 케이스가 하나씩 주어지며, 각 줄에는 정수 N 하나가 주어진다.

각 테스트 케이스에 대해 다음을 출력한다.

Case #X: K

여기서 X는 1부터 시작하는 테스트 케이스 번호이고, K는 목록의 다음 정수이다.