Counting Sheep (Large)

Bleatrix the sheep has a strategy for falling asleep faster.

First, she picks a number $N$. Then she names $N$, $2 \times N$, $3 \times N$, and so on. Each time she names a number, she writes down every digit that appears in it, skipping digits she has already written. Once she has written every digit from 0 to 9, she falls asleep.

Bleatrix starts at $N$, and after naming $i \times N$ she names $(i + 1) \times N$. For example, with $N = 1692$ she proceeds as follows.

• $N = 1692$. She has written 1, 2, 6, 9.
• $2N = 3384$. She has now written 1, 2, 3, 4, 6, 8, 9.
• $3N = 5076$. Every digit is written, so she falls asleep.

What is the last number Bleatrix names before she falls asleep? If she will never fall asleep, print INSOMNIA.

The first line contains the number of cases $T$. Each of the next $T$ lines contains one case: a single number $N$, the number Bleatrix picked.

• $1 \le T \le 100$
• $0 \le N \le 10^6$

For each case, print one line Case #x: y, where $x$ is the case number starting from 1 and $y$ is the last number Bleatrix names, or INSOMNIA.

In the first case of the example, $2 \times 0 = 0$, $3 \times 0 = 0$, and so on, so Bleatrix can never write any digit other than 0. She never falls asleep.

In the second case, she names 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, and 0 is the last digit written. The last number is 10.

In the third case, she names 2, 4, 6, and so on. She cannot write the digit 9 before 90. When she names 90, she has already written every digit from 0 to 8, so the last number is 90.

In the fourth case, she names 11, 22, 33, 44, 55, 66, 77, 88, 99, 110, so the last number is 110.

The fifth case is the number described in the statement.