2019 ICPC Asia Danang Regional Contest

Start

2019-12-06 01:20 UTC

2019 ICPC Asia Danang Regional Contest

End

2019-12-06 06:20 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -114 days 13:15:43

Time elapsed

5:00:00

Time remaining

0:00:00

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$:

  1. Increase $a$ by $1$, i.e. assigning

    a := a + 1
  2. 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