1의 변환

수의 왕국(Numeracija) 은 자기 나라 수들의 품질을 매우 자랑스러워하여, 주민이 어떤 수를 한 번 바꿀 때마다 세금을 걷는다. 그런데도 이 왕국의 주민들은 수를 변형하는 것을 무척 좋아한다.

하나조(Vienetukai) 라는 친구들 모임은 언제나 수 $1$ 에서 시작해 수를 변형하기를 즐긴다. 이들은 넉넉하지 못하기 때문에, 가장 마지막(가장 낮은 자리) 숫자에만 작용하는 가장 저렴한 변형만 사용한다.

• 수의 마지막 숫자에 $1$ 을 더한다 — 금화 $1$ 개;
• 수의 마지막 숫자를 $2$ 부터 $9$ 까지의 정수 중 하나로 곱한다 — 금화 $2$ 개.

변형은 언제나 마지막 한 자리 숫자에만 작용하며, 그 결과가 그 자리를 대신한다(곱셈 결과가 두 자리이면 수는 그만큼 길어진다). 예를 들어 $7$ 의 마지막 숫자에 $3$ 을 곱하면 $7$ 은 $21$ 이 되고, $25$ 의 마지막 숫자 $5$ 에 $3$ 을 곱하면 $5$ 가 $15$ 로 바뀌어 $215$ 가 된다.

예를 들어 이 연산들을 사용하면 $1$ 에서 다음과 같은 변형 순서로 $2121$ 을 얻을 수 있다.

1. $1$ 에 $7$ 을 곱해 $7$ 을 얻는다.
2. $7$ 에 $3$ 을 곱해 $21$ 을 얻는다.
3. 마지막 숫자에 $1$ 을 더해 $22$ 를 얻는다.
4. 마지막 숫자에 $5$ 를 곱해 $210$ 을 얻는다.
5. 마지막 숫자에 $1$ 을 더해 $211$ 을 얻는다.
6. 마지막 숫자에 $3$ 을 곱해 $213$ 을 얻는다.
7. 마지막 숫자에 $7$ 을 곱해 $2121$ 을 얻는다.

이 변형의 비용은 금화 $12$ 개이며, 다음과 같이 도식으로 나타낼 수 있다.

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

$2121$ 은 더 저렴하게, 금화 $9$ 개만으로도 얻을 수 있다.

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

하나조 가 돈을 아낄 수 있도록 도와주자. 주어진 수 $A$ 를 위 변형들만으로 $1$ 에서 얻는 데 드는 최소 비용을 구하여라.

첫째 줄에 자연수 $A$ 가 주어진다.

하나조 가 $1$ 에서 수 $A$ 를 얻기 위한 최소 비용을 정수 하나로 출력한다. 주어진 변형들로 $A$ 를 얻는 것이 불가능하면 $-1$ 을 출력한다.

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