The Next Number (Large)

For each digit $i$ from 1 to 9, let $D_i$ be the number of times $i$ occurs in the decimal representation of $N$. You write out, in ascending order, every positive integer whose decimal representation contains the digit $i$ exactly $D_i$ times for every $i$ from 1 to 9. The number of times the digit 0 occurs is not restricted. No number has a leading zero.

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

You are given $N$, the last number you wrote. 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 a single integer $N$.

Limits

• $1 \le T \le 500$
• $1 \le N \le 10^{20}$

For each test case, print one line in the following format.

Case #X: K

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