Pred vama je mašina koja ima displej i dva dugmeta, koja su obeležena sa + i *. Pritiskom na dugme + broj na displeju se uvećava za 1, dok se pritiskom na dugme * broj na displeju duplira. Na displeju je na početku ispisan broj 0, potrebno je odrediti minimalan broj operacija nakon kojih će na displeju biti ispisan zadati broj. Mašina zna da izvršava aritmetičke operacije samo nad heksadekadnim brojevima, pa će i broj koji treba dobiti biti zadat u heksadekadnom obliku.

Opis ulaza

U prvoj liniji standardnog ulaza unosi se broj ~N~ (~1 \le N \le 10^5~), koji označava dužinu(broj cifara) heksadekadnog broja. U drugoj liniji standardnog ulaza unosi se N karaktera, koji mogu biti cifre (0-9), ili velika slova (A-F), koji predstavljaju cifre broja zapisanog u heksadekadnom sistemu.

Opis izlaza

U prvoj i jedinoj liniji standardnog izlaza minimalan broj operacija koji je potreban da bi se napravio broj.

Primer

1
6

4

2
1A

7

Objašnjenje test primera

U prvom test primeru broj 6 se može napraviti pomoću 4 operacije. Prvo primenjujemo sabiranje, zatim množenje, nakon toga sabiranje, i na kraju ponovo množenje.
(((0+1)×2)+1)×2 = 6
U drugom test primeru minimalan broj operacija je 7.

Ograničenja i podzadaci

(~1 \le N \le 10^5~)

Test primeri su podeljeni u 5 disjunktnih grupa:
U test primerima vrednim 5 poena (~1 \le N \le 2~).
U test primerima vrednim 10 poena: (~1 \le N \le 5~).
U test primerima vrednim 20 poena: (~1 \le N \le 300~).
U test primerima vrednim 25 poena: (~1 \le N \le 3000~).
U test primerima vrednim 40 poena: Nema dodatnih ograničenja.