Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: kvadr_bit.in

Rezultatų failas: kvadr_bit.out

Jei norite pateikti savo sprendimą - prisijunkite.

Kvadrato bitai

Jums duotas skaičius n. Nagrinėkime jo dvejetainę išraišką be nulių skaičiaus priekyje (pavyzdžiui, 10_{10}=1010_2). Kiek yra būdų perstatyti šios dvejetainės išraiškos skaitmenis, kad gautas skaičius būtų kokio nors sveikojo skaičiaus kvadratas? Pavyzdžiui, jei n=10_{10}=1010_2, yra vienintelis būdas: 1010_2\\rightarrow1001_2=9=3^2. Neleidžiama perstatyti skaitmenis taip, kad atsirastų nulis skaičiaus pradžioje arba gautas skaičius būtų didesnis nei 10^{18}.

Pradiniai duomenys

Vienintelėje eilutėje bus pateiktas skaičius n (1\\leqn\\leq10^{18}).

Rezultatai

Išveskite skaičių būdų perstatyti skaičiaus n bitus taip, kad gautume sveikojo skaičiaus kvadratą.

Pavyzdžiai

Duomenys Rezultatai 
9
 
1
 
10
 
1
 
2
 
0
 
1000000000000000000
 
12206114