7227번 - Vieneto transformacija 다국어

문제

Numeracijos karalystė labai didžiuojasi savo skaičių kokybe, tad renka mokesčius iš savo gyventojų už kiekvieną skaičiaus pakeitimą. Nepaisant to, Numeracijos gyventojai labai mėgsta transformuoti skaičius.

Draugų grupė Vienetukai savoms reikmėms naudoja pačias pigiausias transformacijas:

• prie skaičiaus pirmo (labiausiai reikšminio) ar paskutinio (mažiausiai reikšminio) skaitmens pridėti vienetą – kainuoja 1ドル$ auksinį;
• skaičiaus pirmą ar paskutinį skaitmenį padauginti iš bet kurio skaitmens nuo 2ドル$ iki 9ドル$ – kainuoja 2ドル$ auksinius.

Vienetukai visada pradeda savo transformacijas nuo skaičiaus 1ドル$.

Pavyzdžiui, šiuos metus 2021ドル$ iš 1ドル$ galima gauti tokia transformacijų seka:

1. Prie 1ドル$ pridėsime 1ドル$ – gauname 2ドル$.
2. 2ドル$ padauginame iš 5ドル$ – gauname 10ドル$.
3. Prie pirmo skaitmens pridedame 1ドル$ – gauname 20ドル$.
4. Pirmą skaitmenį padauginame iš 5ドル$ – gauname 100ドル$.
5. Pirmą skaitmenį padauginame iš 2ドル$ – gauname 200ドル$.
6. Prie paskutinio skaitmens pridedame 1ドル$ – gauname 201ドル$.
7. Paskutinį skaitmenį padauginame iš 5ドル$ – gauname 205ドル$.
8. Paskutinį skaitmenį padauginame iš 4ドル$ – gauname 2020ドル$.
9. Prie paskutinio skaitmens pridedame 1ドル$ – gauname 2021ドル$.

Tokia transformacija kainuoja 14ドル$ auksinių. Šią seką galime pavaizduoti schematiškai:

$$ 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 \text{.} $$

Skaičių 2021ドル$ galima buvo gauti ir pigiau, sumokant tik 9ドル$ auksinius:

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

Padėkite Vienetukams gauti $M$ duotųjų skaičių nurodytomis transformacijomis.

Kiekvienam iš $M$ $n$-ženklių skaičių $A_i,ドル raskite mažiausią kainą, už kurią Vienetukai gali gauti $A_i$ iš 1ドル$.

입력

Pirmoje įvesties eilutėje duotas skaičius $M$ – rinkinio skaičių kiekis. Likusiose $M$ eilutėse įrašyti natūralieji skaičiai $A_i$ (1ドル ≤ i ≤ M$).

출력

Atskirose eilutėse pateikite $M$ skaičių – atitinkamas mažiausias vieneto transformacijų kainas. Jeigu tam tikriems skaičiams atitinkamos vieneto transformacijos neegzistuoja, tose eilutėse išveskite $-1$.

제한

• 1ドル ≤ M ≤ 50$
• 1ドル ≤ A_i ≤ 10^{19}$

힌트