Problem G
Generating Numbers
Ging is working on the next generation of computers – ‘Tanquum computers’.
‘Tanquum computers’ take advantages of advanced Physics, allowing them to rearrange the digits of every positive integer in one instruction.
The application is limitless. For example, from number $1$, ‘Tanquum computers’ are able to generate every positive integer $x$, using only two types of instructions: increment and rearrangement.
More precisely, only the following two operations are allowed on an integer $a$:
-
Increase $a$ by $1$, i.e. assigning
a := a + 1
-
Rearrange the digits of $a$. The result must not have any leading zeroes. For example, from $102$, using one instruction of this type, you can get any of the following numbers: $102, 120, 201, 210$.
As ‘Tanquum computers’ is very advanced, it only uses a minimum number of instructions.
You have recently been hired by Ging to help with the development of ‘Tanquum computers’. Your first task is to verify the correctness of ‘Tanquum computers’. Given some number $x$, you need to find the minimum number of instructions it would take to transform $1$ into $x$.
Input
The first line of input contains a single integer $t$ $(1 \le t \le 1\, 000)$ — the number of test cases.
In the next $t$ lines, each line contains a single integer $x$ $(1 \le x \le 10^9)$.
Output
For each test case, print a single line containing the minimum number of instructions.
Explanation of Sample data
-
In the first example, it takes $4$ increments to generate the number $5$.
-
In the second example, you can generate $26$ by applying the following $17$ instructions:
-
$11$ increments to get $12$,
-
$1$ rearrangement to get $21$,
-
$5$ increments to get $26$.
-
| Sample Input 1 | Sample Output 1 |
|---|---|
3 5 26 843 |
4 17 44 |
