Злым числом в математике называется неотрицательное целое число с чётным числом единиц в его двоичной записи (например, число 5 — злое, в его двоичной записи две единицы). Они используются в теории чисел при исследовании последовательности Морса–Туэ и применяются в алгоритмах фрактального сжатия изображений.

Натуральное число будем называть очень злым, если само оно чётное и количество единиц в его двоичной записи также чётное. Это такие числа, как 6, 10, 12, 18, 20 и так далее.

По данному $$$n$$$ определите количество очень злых чисел, не превосходящих $$$n$$$.

Решения, правильно работающие, когда число $$$n$$$ не превосходит $$$10^{5}$$$, будут оцениваться в 30 баллов.

Решения, правильно работающие, когда число $$$n$$$ является точной степенью числа $$$2$$$, будут оцениваться в 30 баллов.