Lucian are S metri patrati de tesut din care vrea sa faca perne. Pentru o perna de latime N (numar natural, N >= 1) este nevoie de exact 2NN metri patrati de tesut.
Lucian foloseste tesutul astfel: la fiecare pas, face cea mai mare perna posibila din tesutul ramas, adica alege cel mai mare N natural pentru care 2NN este cel mult cantitatea de tesut ramasa, apoi consuma acei 2NN metri patrati. Repeta procedeul cu tesutul ramas.
Daca la un moment dat mai ramane tesut, dar acesta este insuficient pentru a face macar o perna de latime 1 (adica mai putin de 2 metri patrati raman si totusi nu e zero), procesul esueaza.
Cerinta: determinati numarul total de perne pe care le poate face Lucian, sau afisati -1 daca la un moment dat ramane tesut nefolosit din care nu se mai poate face nicio perna.
- Date de intrare
- Se citeste, pe o singura linie, numarul natural S.
- Date de iesire
- Se afiseaza numarul total de perne facute, sau -1 daca nu tot tesutul poate fi folosit.
- Restrictii
- 1 <= S <= 10^12
Exemple
Exemplul 1
Intrare
1234
Iesire
4
Exemplul 2
Intrare
1
Iesire
-1