Bleatrix Trotter the sheep has devised a strategy that helps her fall asleep faster. First, she picks a number . Then she starts naming , , , and so on. Whenever she names a number, she thinks about all of the digits in that number. She keeps track of which digits and she has seen at least once so far as part of any number she has named. Once she has seen each of the ten digits at least once, she will fall asleep.
Bleatrix must start with and must always name directly after . For example, suppose that Bleatrix picks . She would count as follows:
- . Now she has seen the digits and .
- . Now she has seen the digits and .
- . Now she has seen all ten digits, and falls asleep.
What is the last number that she will name before falling asleep? If she will count forever, print INSOMNIA
instead.
Input Specification
The first line of the input gives the number of test cases, . test cases follow. Each consists of one line with a single integer , the number Bleatrix has chosen.
Output Specification
For each test case, output one line containing Case #x: y
, where is the test case number (starting from 1) and is the last number that Bleatrix will name before falling asleep, according to the rules described in the statement.
Limits
Time limit: 20 seconds per test set.
Memory limit: 1 GB.
.
Small dataset
.
Large dataset
.
Sample Input
5
0
1
2
11
1692
Sample Output
Case #1: INSOMNIA
Case #2: 10
Case #3: 90
Case #4: 110
Case #5: 5076
In Case #1, since , , and so on, Bleatrix will never see any digit other than , and so she will count forever and never fall asleep. Poor sheep!
In Case #2, Bleatrix will name . The will be the last digit needed, and so she will fall asleep after .
In Case #3, Bleatrix will name and so on. She will not see the digit in any number until , at which point she will fall asleep. By that point, she will have already seen the digits and which will have appeared for the first time in the numbers and respectively.
In Case #4, Bleatrix will name and then fall asleep.
In Case #5, Bleatrix will name and before falling asleep. Case #5 is the one described in the problem statement. Note that it would only show up in the Large dataset, and not in the Small dataset.
Comments