Janosik

Limit pamięci: 128 MB

Jak wiadomo, Janosik zabiera bogatym, by rozdawać biednym. Wraz ze swoją bandą złupił właśnie konwój, który przewoził złoto do zamku murgrabiego. Łupem zbójów padło szkatułek. Po przetransportowaniu ich do jaskini bandy okazało się, że -ta szkatułka (dla ) zawiera dokładnie mieszków ze złotem.

Gdy do Janosika przychodzi biedak, prosząc o kilka złotych dukatów, Janosik stosuje następującą procedurę. Najpierw wybiera niepustą szkatułkę, która zawiera najmniej mieszków ze złotem. Jeśli jest w niej dokładnie jeden mieszek, Janosik wręcza go biedakowi, a ten odchodzi uradowany. W przeciwnym przypadku, jeśli w szkatułce znajduje się nieparzysta liczba mieszków, to Janosik chowa jeden z nich do kieszeni i zaczyna całą procedurę od nowa. Jeśli zaś w szkatułce znajduje się parzyście wiele mieszków, Janosik wyjmuje dokładnie połowę z nich ze szkatułki, przekłada je do jednej z pustych szkatułek (szczęśliwie w jaskini jest ich pod dostatkiem) i zaczyna całą procedurę od nowa. Tak więc jeśli biedak przybędzie do Janosika, gdy ten będzie miał jeszcze jakąś niepustą szkatułkę, to w wyniku (być może wielokrotnego) zastosowania procedury przez Janosika biedak na pewno otrzyma mieszek ze złotem. Biedacy przychodzą do jaskini Janosika tak długo, aż wszystkie szkatułki zostaną opróżnione.

Zbóje z bandy Janosika zastanawiają się, czy ich przywódca swoim postępowaniem nie narusza dobrego imienia zbójów. Chcieliby wiedzieć, ile złupionych mieszków pozostanie w kieszeni Janosika po opróżnieniu wszystkich szkatułek.

Wejście

W pierwszym i jedynym wierszu wejścia znajduje się jedna liczba całkowita (), która oznacza liczbę szkatułek zrabowanych przez bandę Janosika.

Wyjście

W pierwszym i jedynym wierszu wyjścia należy wypisać liczbę całkowitą oznaczającą liczbę mieszków ze złotem, które pozostaną w kieszeni Janosika po opróżnieniu wszystkich szkatułek.

Przykład

Dla danych wejściowych:

5

poprawną odpowiedzią jest:

2

Autor zadania: Tomasz Idziaszek