Counter Culture (Small)

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 keeps saying the number that is 1 greater than the number she just said, and stops once she has said $N$.

It is your turn now. You find the routine tedious, so you add a twist that speeds it up. Instead of adding 1 to the previous number, you may reverse its digits, dropping any leading zeros the reversal creates. After saying 16 you may say either 17 or 61. After saying 2300 you may say either 2301 or 32. Within one performance you may reverse as many times as you want, or not at all.

The first number you say must be 1. What is the fewest numbers you need to say in order to reach $N$? Both 1 and $N$ count toward that 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^6$

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 fewest numbers you need to say.

For $N = 19$, reversing never helps, so counting straight up to 19 is optimal.

For $N = 23$, the best plan is to count up to 12, reverse to 21, then keep counting to 23. The numbers said are 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 21, 22, 23.