Licznik Piotrka

autor: Marcin Pilipczuk

Piotrek startuje w wielu konkursach ACM-owych z bardzo dobrymi wynikami. Jednym z bardzo ważnych elementów jego strategii jest zapeszanie i denerwowanie przeciwników piszących na tej samej sali co on. W tym celu skonstruował sobie duży licznik, na którym ogłasza innym, ile zadań już zrobił, ale, aby jeszcze bardziej objawić geniusz twórcy, licznik pokazuje liczbę zrobionych zadań w systemie o podstawie 2. Budowa licznika nie jest bardzo skomplikowana - jest to rządek wielu tabliczek, każda ma z jednej strony narysowaną jedynkę, a z drugiej zero, każdą tabliczkę można niezależnie od innych przekręcić o 180 stopni. Tabliczki te reprezentują liczbę w systemie binarnym. Na początku konkursu licznik ustawiony jest na zero (czyli wszystkie tabliczki pokazują zero). Piotrek w momencie jak zrobi zadanie triumfalnie przestawia licznik na nową wartość, nie kręcąc bez potrzeby tabliczkami, choć czasem musi całkiem sporo tabliczek przekręcić.

Piotrek niestety w czasie ostatniego konkursu nie zajął pierwszego miejsca, mimo że zrobił całkiem sporo zadań. Obawia się, że jest to spowodowane tym, że za dużo czasu spędził na przekręcaniu tabliczek. Piotrek w czasie konkursu zrobił n zadań. Ile razy wykonał przekręcenie pojedynczej tabliczki? (włącznie z ostatnim rozwiązanym zadaniem)

Zadanie

Napisz program, który:

Wejście

W pierwszym i jedynym wierszu wejścia jest podana jedna liczba całkowita 0<=n<=10100, oznaczająca liczbę rozwiązanych przez Piotrka zadań.

Wyjście

W pierwszym i jedynym wierszu wyjścia powinieneś wypisać liczbę k - oznaczającą, ile razy Piotrek przekręcał tabliczki.

Przykład 1

Dla pliku wejściowego:

13

Twój program powinien wypisać:

23

Przykład 2

Dla pliku wejściowego:

1234567890

Twój program powinien wypisać:

2469135768