Злым числом в математике называется неотрицательное целое число с чётным числом единиц в его двоичной записи (например, число 5 — злое, в его двоичной записи две единицы). Они используются в теории чисел при исследовании последовательности Морса–Туэ и применяются в алгоритмах фрактального сжатия изображений. Натуральное число будем называть очень злым, если само оно чётное и количество единиц в его двоичной записи также чётное. Это такие числа, как 6, 10, 12, 18, 20 и так далее. По данному n определите количество очень злых чисел, не превосходящих n.
Формат входных данных
Единственная строка входного файла содержит натуральное число n (1 ≤ n ≤ 10
9 ).
Формат выходных данных
Выведите одно неотрицательное целое число — количество очень злых натуральных чисел, не превосходящих n.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
20
|
5
|