E. Үзэсгэлэнт задрал

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Валера тоог $2^k$ юм уу $-2^k$-тай $(k≥0)$ тэнцүү байвал үзэсгэлэнтэй гэдэг. Саяхан математикийн багш нь түүнээс $n$ тоог үзэсгэлэнт тоонуудын нийлбэрт задлах даалгавар өгсөн. Валера залхуу учир аль болох цөөхөн үзэсгэлэнт тоо ашиглахыг хүсчээ. Түүнд туслана уу.

Оролт

Эхний мөрөнд тэгээр эхлээгүй $n$ $(n>0)$ тоог 2-тын тооллын системд бичсэн $s$ $(1≤|s|≤10^6)$ тэмдэгт мөр өгөгдөнө.

Гаралт

$n$ тоог үзэсгэлэнт тоонуудаар задлахад шаардлагатай хамгийн бага тоонуудын тоог хэвлэнэ.

Орчуулсан: Говьхүү

Жишээ тэстүүд

Оролт
10
Гаралт
1
Оролт
111
Гаралт
2
Оролт
1101101
Гаралт
4

Тэмдэглэл

In the first sample $n = 2$ is a beautiful number.

In the second sample $n = 7$ and Valera can decompose it into sum $2^{3} + ( - 2^{0})$.

In the third sample $n = 109$ can be decomposed into the sum of four summands as follows: $2^{7} + ( - 2^{4}) + ( - 2^{2}) + 2^{0}$.

Сэтгэгдлүүдийг ачааллаж байна...