Unit Transformation

The kingdom of Numeracija takes great pride in the quality of its numbers, so it collects a tax from its citizens for every change made to a number. Even so, the citizens of Numeracija love transforming numbers.

A group of friends called the Vienetukai ("the Ones") love transforming numbers, always starting from the number $1$. Because they are not wealthy, they use only the cheapest transformations, which act only on the last (least significant) digit:

• add $1$ to the last digit of the number — costs $1$ gold;
• multiply the last digit of the number by any integer from $2$ to $9$ — costs $2$ gold.

A transformation always acts on the single last digit, and its result takes the place of that digit (so a two-digit product simply lengthens the number). For example, multiplying the last digit of $7$ by $3$ turns $7$ into $21$, and multiplying the last digit of $25$ (which is $5$) by $3$ replaces $5$ with $15$, giving $215$.

For example, using these operations the number $2121$ can be obtained from $1$ by the following sequence of transformations:

1. Multiply $1$ by $7$ to get $7$.
2. Multiply $7$ by $3$ to get $21$.
3. Add $1$ to the last digit to get $22$.
4. Multiply the last digit by $5$ to get $210$.
5. Add $1$ to the last digit to get $211$.
6. Multiply the last digit by $3$ to get $213$.
7. Multiply the last digit by $7$ to get $2121$.

This transformation costs $12$ gold and can be shown schematically as:

$1 \underset{1 \times 7}{\overset{2}{\Longrightarrow}} 7 \underset{7 \times 3}{\overset{2}{\Longrightarrow}} 21 \underset{1 +1}{\overset{1}{\Longrightarrow}} 22 \underset{2 \times 5}{\overset{2}{\Longrightarrow}} 210 \underset{0 + 1}{\overset{1}{\Longrightarrow}} 211 \underset{1 \times 3}{\overset{2}{\Longrightarrow}} 213 \underset{3 \times 7}{\overset{2}{\Longrightarrow}} 2121$

The number $2121$ could also be obtained more cheaply, for only $9$ gold:

$1 \underset{1 \times 5}{\overset{2}{\Longrightarrow}} 5 \underset{5 \times 5}{\overset{2}{\Longrightarrow}} 25 \underset{5 \times 3}{\overset{2}{\Longrightarrow}} 215 \underset{5 \times 4}{\overset{2}{\Longrightarrow}} 2120 \underset{0 +1 }{\overset{1}{\Longrightarrow}} 2121$

Help the Vienetukai save money: find the minimum cost for which they can obtain the given number $A$ from $1$ using the described transformations.

The first line contains a natural number $A$.

Output a single integer — the minimum cost for which the Vienetukai can obtain the given number $A$ from $1$. If $A$ cannot be obtained using the described transformations, output $-1$.

• $1 \le A \le 10^9$