Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Jei norite pateikti savo sprendimą - prisijunkite.

Kolatso uždavinys

Jums duotas skaičius n, kur 1\\leqn\\leq10^5. Kiekvienu žingsniu privalote padaryti vieną iš šių operacijų:

  • Jei skaičius n lyginis, jį pakeisti į \\frac{n}{2}
  • Jei skaičius n nelyginis, jį pakeisti į 3n+1
Galima įrodyti, kad su visais n, kai 1\\leqn\\leq10^5, po kažkiek žingsnių, n taps lygus 1-etui per mažiau nei 1000 žingsnių. Jūsų užduotis - suskaičiuoti, kiek žingsnių prireiks, kad n taptų vienetu.

Pradiniai duomenys

Pirmoje eilutėje įrašytas vienintelis skaičius n.

Rezultatai

Išveskite, kiek žingsnių prireiks.

Pavyzdžiai

Duomenys Rezultatai Paaiškinimas 
1
 
0
 Nereikės atlikti žingsnių, nes n jau yra 1 
2
 
1
 
 2-> 1
 
3
 
7
 
 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
 
4
 
2
 
 4 -> 2 -> 1