1에서 시작하는 변환

뉴메리아 왕국은 자국 수(數)의 품질에 큰 자부심을 가지고 있어서, 수를 한 번 바꿀 때마다 주민에게 세금을 걷습니다. 그럼에도 뉴메리아 주민들은 수를 변환하는 것을 무척 좋아합니다.

일원회(Units) 라는 친구들은 가장 값싼 변환만을 사용합니다. 수는 맨 앞자리에 $0$ 이 없는 십진법으로 적으며, 오직 맨 앞자리(가장 큰 자리)나 맨 뒷자리(가장 작은 자리) 숫자만 바꿀 수 있습니다.

• 맨 앞자리 또는 맨 뒷자리 숫자 $d$ 에 $1$ 을 더해, 그 자리를 $d+1$ 의 십진 표기로 바꿉니다. 비용은 금화 $1$ 개입니다. ($d=9$ 이면 $d+1=10$ 이므로 숫자 "9"가 두 자리 "10"으로 바뀌어 수의 길이가 늘어납니다.)
• 맨 앞자리 또는 맨 뒷자리 숫자 $d$ 에 $2$ 부터 $9$ 까지의 숫자 $k$ 를 곱해, 그 자리를 $d \times k$ 의 십진 표기로 바꿉니다. 비용은 금화 $2$ 개입니다. ($d \times k \ge 10$ 이면 그 자리는 두 자리 숫자로 바뀝니다.)

일원회는 항상 수 $1$ 에서 변환을 시작합니다.

예를 들어 $2021$ 은 다음 순서로 $1$ 에서 얻을 수 있으며, 금화 $14$ 개가 듭니다.

1. $1$ 에 $1$ 을 더해 $2$ 를 얻습니다.
2. $2$ 에 $5$ 를 곱해 $10$ 을 얻습니다.
3. 맨 앞자리에 $1$ 을 더해 $20$ 을 얻습니다.
4. 맨 앞자리에 $5$ 를 곱해 $100$ 을 얻습니다.
5. 맨 앞자리에 $2$ 를 곱해 $200$ 을 얻습니다.
6. 맨 뒷자리에 $1$ 을 더해 $201$ 을 얻습니다.
7. 맨 뒷자리에 $5$ 를 곱해 $205$ 를 얻습니다.
8. 맨 뒷자리에 $4$ 를 곱해 $2020$ 을 얻습니다.
9. 맨 뒷자리에 $1$ 을 더해 $2021$ 을 얻습니다.

아래 그림에서 화살표 위의 수는 그 단계의 비용이고, 아래의 식은 적용한 연산입니다.

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

하지만 $2021$ 은 더 싸게, 금화 $9$ 개만으로도 얻을 수 있습니다.

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

일원회가 주어진 $M$ 개의 수를 이 변환들로 얻을 수 있도록 도와주세요.

각 수 $A_i$ 에 대해, 일원회가 $1$ 에서 $A_i$ 를 얻는 데 드는 최소 비용을 구하세요. 어떤 변환 순서로도 얻을 수 없는 수라면 그 답은 $-1$ 입니다.

첫 번째 줄에 정수 $M$ — 수의 개수가 주어집니다. 이어지는 $M$ 개의 줄에는 각각 하나의 자연수 $A_i$ ($1 \le i \le M$) 가 주어집니다.

$M$ 개의 줄을 출력합니다. $i$ 번째 줄에는 $1$ 에서 $A_i$ 를 얻는 단위 변환의 최소 비용을 출력합니다. 어떤 수에 대해 그러한 변환이 존재하지 않으면 그 줄에 $-1$ 을 출력합니다.

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