SPOJ in Armenian

Տրված x-ից x³¹ աստիճանը կարելի է հաշվել x-ը 30 անգամ իրենով բազմապատկելով.

x² = x × x,   x³ = x² × x,  x⁴ = x³ × x, …, x³¹ = x³⁰ × x

Հաշվի առնելով, որ քառակուսի բարձրացնելը կրճատում է բազմապատկումների հաջորդականությունը, կարելի է x³¹-ը հաշվել ութ բազմապատկման միջոցով.

x² = x × x,  x³ = x² × x,  x⁶ = x³ × x³,  x⁷ = x⁶ × x,  x¹⁴ = x⁷ × x⁷, x¹⁵ = x¹⁴ × x,  x³⁰ = x¹⁵ × x¹⁵,  x³¹ = x³⁰ × x

Սա x³¹-ը հաշվելու ամենակարճ եղանակը չէ։ Միայն յոթ բազմապատկումների միջոցով հաշվելու շատ եղանակներ կան։ Օրինակ, հետևյալ կերպ.

x² = x × x,  x⁴ = x² × x²,  x⁸ = x⁴ × x⁴,  x¹⁰ = x⁸ × x², x²⁰ = x¹⁰ × x¹⁰, x³⁰ = x²⁰ × x¹⁰, x³¹ = x³⁰ × x

Ավելի քիչ բազմապատկումների թվով հնարավոր չէ հաշվել x³¹-ը։ Այնպես որ, սա միայն բազմապատկումների միջոցով x³¹-ը հաշվելու ամենաարդյունավետ եղանակներից մեկն է։

Բայց եթե թույլատրվի օգտագործել նաև բաժանում, գործողությունների քանակը կարելի է կրճատել։ x³¹-ը կարելի է հաշվել 6 գործողության (5 բազմապատկման և 1 բաժանման) միջոցով.

x² = x × x, x⁴ = x² × x², x⁸ = x⁴ × x⁴, x¹⁶ = x⁸ × x⁸,  x³² = x¹⁶ × x¹⁶, x³¹ = x³² ÷ x

Սա x³¹-ը հաշվելու ամենաարագ եղանակներից մեկն է, եթե բաժանումը նույնքան արագ կատարվի, որքան բազմապատկումը։

Պահանջվում է գրել ծրագիր, որը գտնի, թե տրված n-ի համար առնվազն քանի բազմապատկման և բաժանման գործողությունների միջոցով է կարելի հաշվել xⁿ-ը ։

Մուտքը

Մուտքի յուրաքանչյուր տողում տրված է մի n բնական թիվ, որը չի գերազանցումը 1000-ը։ Մուտքային տվյալներն ավարտվում են 0-ով, որը պետք չէ մշակել։

Ելքը

Ելքում, մուտքային յուրաքանչյուր n թվի համար հարկավոր է արտածել մի թիվ՝ x-ից սկսած xⁿ-ը բազմապատկման և բաժանման միջոցով ստանալու համար մինիմալ գործողությունների քանակը։

Օրինակ

Մուտքը.
31
1
0
 Ելքը.
6
0