 The Next Number

Round 1B, 2009

Submit Solution(Code Jam Page)

Problem

You are writing out a list of numbers. Your list contains all numbers with exactly Di digits in its decimal representation which are equal to i, for each i between 1 and 9, inclusive. You are writing them out in ascending order.

For example, you might be writing every number with two '1's and one '5'. Your list would begin 115, 151, 511, 1015, 1051.

Given N, the last number you wrote, compute what the next number in the list will be.

Input

The first line of input contains an integer T, the number of test cases in the input. T lines follow, one for each test case, each containing a single integer N.

Output

For each test case, output

Case #X: K
where X is the test case number, starting from 1, and K is the next integer in the list.

Limits

Small dataset

1 ≤ T ≤ 50
1 ≤ N ≤ 106

Large dataset

1 ≤ T ≤ 500
1 ≤ N ≤ 1020

Sample

 Input Output 3 115 1051 6233 Case #1: 151 Case #2: 1105 Case #3: 6323

Points Correct Attempted
9pt 2559 3329
26pt 1890 2557

Subscribe to our newsletter

Join our monthly newsletter and never miss out on new stories and promotions.