В подземелье живут гномы. У них есть древняя традиция деления золота:
Когда гном получает N монет:
1. Если N = 0, гном грустит и ничего не делает
2. Если N = 1, гном оставляет монету себе и кричит "
МОЁ!"
3. Если N > 1:
- Гном берёт себе 1 монету и кричит "
МОЁ!"
- Остальные (N-1) монет делит пополам
- Левую половину (N-1)/2 отдаёт левому ученику-гному
- Правую половину (N-1) - (N-1)/2 отдаёт правому ученику-гному
- Каждый ученик делает то же самое по традиции
Подсчитайте, сколько раз прозвучит крик "
МОЁ!" при делении N монет.
ВХОДНЫЕ ДАННЫЕ:
Одно число N (0 ≤ N ≤ 10^9) - начальное количество монет.
ВЫХОДНЫЕ ДАННЫЕ:
Одно число - сколько раз прозвучит "МОЁ!"
Примеры
| № | Входные данные | Выходные данные |
|
1
|
0
|
0
|
|
2
|
1
|
1
|
|
3
|
7
|
7
|