Problem

You are writing out a list of numbers. Your list contains all numbers with exactly D_i 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

Limits

Memory limit: 1 GB.

Small dataset (9 Points)

Time limit: 20 2 seconds.

1 ≤ T ≤ 50

1 ≤ N ≤ 10⁶

Large dataset (26 Points)

Time limit: 30 4 seconds.

1 ≤ T ≤ 500

1 ≤ N ≤ 10²⁰

Sample

3
115
1051
6233

Case #1: 151
Case #2: 1105
Case #3: 6323