Duletu je bilo jako dosadno na času matematike (ne zato što ga gradivo ne interesuje već zato što je većinu prešao kada se pripremao za takmičenje) tako da je rešio da se malo poigra. Naime, rekao je svom drugu da napiše veliki prirodni broj n na papiru i tvrdio da može samo uz pomoć operacija: dodavanja broja 1 datom broju, oduzimanja broja 1 od datog broja i njegovim deljenjem sa 2 (ukoliko je paran) - dobiti broj 0. Kako njegovo rešenje mora stati na jednom papiru, Dule mora da nađe najmanji broj operacija koje dovode broj n na 0.

Kako je Dule uvideo da ovo nije toliko jednostavan problem, zamolio vas je da napišete program koji nalazi traženi minimalni broj operacija.

Ulaz.

(Ulazni podaci se učitavaju sa standardnog ulaza) U prvom i jednom redu ulazne datoteke nalazi se prirodni broj n. Broj n neće imati više od 1000 cifara. Broj neće imati vodećih nula.

Izlaz.

(Izlazni podaci se ispisuju na standardni izlaz) U prvi i jedini red izlazne datoteke upisati minimalni broj operacija potrebnih da se prirodni broj n svede na nulu. Operacije su dodavanje ili oduzimanje jedinice i deljenje sa dva, ukoliko je broj paran.

Primer 1.

5

4

Objašnjenje.

Minimalni broj operacija potrebnih da se broj 5 dovede na nulu je 4. Jedinialgoritam koji sadrži 4 operacija je:

5 → 4 → 2 → 1 → 0

Primer 2.

30

7