Tidy Numbers (Large)

Tatiana likes to keep things tidy. Her toys are sorted from smallest to largest, her pencils from shortest to longest, and her computers from oldest to newest. One day, while practicing her counting, she noticed that some integers have their digits in non-decreasing order when written in base 10 with no leading zeroes. Examples are 8, 123, 555, and 224488. She decided to call such an integer a tidy number. Numbers without this property, such as 20, 321, 495, and 999990, are not tidy.

She has just counted every positive integer from 1 to $N$ in ascending order. What was the last tidy number she counted?

The first line contains the number of test cases $T$. Each of the next $T$ lines describes one test case with a single integer $N$, the last number Tatiana counted.

Limits

• $1 \le T \le 100$
• $1 \le N \le 10^{18}$

For each test case, print one line of the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the last tidy number Tatiana counted.