The Next Number

You write out a list of numbers. For each digit $i$ from 1 to 9, the list holds every positive integer whose decimal representation contains exactly $D_i$ copies of the digit $i$. The number of zeros is not restricted. You write the numbers in ascending order.

For example, if you write every number with two 1s and one 5, the list starts 115, 151, 511, 1015, 1051.

You are given $N$, the last number you wrote. The counts $D_i$ are the digit counts of $N$ itself. Compute the next number in the list.

The first line contains an integer $T$, the number of test cases. Each of the next $T$ lines contains one integer $N$.

Limits

• $1 \le T \le 50$
• $1 \le N \le 10^6$

For each test case, print one line in the form

Case #X: K

where $X$ is the test case number starting from 1 and $K$ is the number that follows $N$ in the list.