Counter Culture (Large)

At the counting poetry slam, a performer takes the microphone, picks a number $N$, and counts aloud from 1 to $N$. She says 1 first, then repeatedly says the number that is 1 greater than the number she just said, and she stops after saying $N$.

It is your turn to perform. Plain counting is tedious, so you add one more move: instead of adding 1 to the last number, you may reverse its digits and say that number, dropping any leading zeros the reversal creates. After saying "16" you may say either "17" or "61", and after saying "2300" you may say either "2301" or "32". You may reverse as many times as you want during a performance, or not at all.

The first number you say must be 1. Find the fewest numbers you need to say in order to reach $N$. Both 1 and $N$ count toward this total. If you say the same number several times, each of those times counts separately.

The first line contains the number of test cases $T$. Each of the next $T$ lines contains one integer $N$, the number you must reach.

Limits

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

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the minimum count of numbers you need to say.

In the second test case of the sample, reversing never helps, so counting straight up to 19 is optimal.

In the third test case, the best plan counts up to 12, reverses to 21, and then counts up to 23. The numbers said are 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 21, 22, 23.