Tidy Numbers#8692
Tatiana likes to keep things tidy. Her toys are sorted from smallest to largest, her pencils are sorted from shortest to longest and her computers from oldest to newest. One day, when practicing her counting skills, she noticed that some integers, when written in base with no leading zeroes, have their digits sorted in non-decreasing order. Some examples of this are , , and . She decided to call these numbers tidy. Numbers that do not have this property, like , , and are not tidy.
She just finished counting all positive integers in ascending order from to . What was the last tidy number she counted?
The first line gives the number of test cases (1 \le t \le 100). lines follow. Each line describes a test case with a single integer (1 \le n \le 10^{18}), the last number counted by Tatiana.
For each test case, output one line containing Case #**: **, where is the test case number (starting from ) and is the last tidy number counted by Tatiana.
Example 1