Transformation from One

The kingdom of Numeria is very proud of the quality of its numbers, so it charges its citizens a tax for every change made to a number. Even so, the people of Numeria love transforming numbers.

A group of friends, the Units, use the cheapest possible transformations. A number is written in decimal without leading zeros, and only its first (most significant) or last (least significant) digit may be changed:

• Add one to the first or last digit $d$, replacing that digit with the decimal representation of $d+1$. This costs $1$ gold coin. (If $d=9$, then $d+1=10$, so the single digit "9" is replaced by the two digits "10" and the number grows longer.)
• Multiply the first or last digit $d$ by any digit $k$ from $2$ to $9$, replacing it with the decimal representation of $d \times k$. This costs $2$ gold coins. (If $d \times k \ge 10$, that digit is replaced by two digits.)

The Units always start from the number $1$.

For example, $2021$ can be obtained from $1$ with the following sequence, costing $14$ gold coins:

1. Add $1$ to $1$ — we get $2$.
2. Multiply $2$ by $5$ — we get $10$.
3. Add $1$ to the first digit — we get $20$.
4. Multiply the first digit by $5$ — we get $100$.
5. Multiply the first digit by $2$ — we get $200$.
6. Add $1$ to the last digit — we get $201$.
7. Multiply the last digit by $5$ — we get $205$.
8. Multiply the last digit by $4$ — we get $2020$.
9. Add $1$ to the last digit — we get $2021$.

In the diagram below, the number above each arrow is the cost of that step and the expression below it is the operation applied.

$$ 1 \underset{1 +1}{\overset{1}{\Longrightarrow}} 2 \underset{2 \times 5}{\overset{2}{\Longrightarrow}} 10 \underset{1 +1}{\overset{1}{\Longrightarrow}} 20 \underset{2 \times 5}{\overset{2}{\Longrightarrow}} 100 \underset{1 \times 2}{\overset{2}{\Longrightarrow}} 200 \underset{0 +1}{\overset{1}{\Longrightarrow}} 201 \underset{1 \times 5}{\overset{2}{\Longrightarrow}} 205 \underset{5 \times 4}{\overset{2}{\Longrightarrow}} 2020 \underset{0+1}{\overset{1}{\Longrightarrow}} 2021 $$

But $2021$ can also be reached more cheaply, for only $9$ gold coins:

$$ 1 \underset{1 \times 9}{\overset{2}{\Longrightarrow}} 9 \underset{9 \times 5}{\overset{2}{\Longrightarrow}} 45 \underset{4 \times 5}{\overset{2}{\Longrightarrow}} 205 \underset{5 \times 4}{\overset{2}{\Longrightarrow}} 2020 \underset{0+1}{\overset{1}{\Longrightarrow}} 2021 $$

Help the Units obtain $M$ given numbers using these transformations.

For each of the $M$ numbers $A_i$, find the least cost for which the Units can obtain $A_i$ starting from $1$. If a number cannot be obtained by any sequence of these transformations, its answer is $-1$.

The first line contains an integer $M$ — the count of numbers in the set. Each of the next $M$ lines contains one natural number $A_i$ ($1 \le i \le M$).

Print $M$ lines. On the $i$-th line print the least cost of the unit transformations that produce $A_i$ from $1$. If no such transformations exist for a given number, print $-1$ on its line.

• $1 \le M \le 50$
• $1 \le A_i \le 10^{19}$