| Author: | Антон Карабанов | Time limit: | 1 sec | |
| Input file: | Standard input | Memory limit: | 256 Mb | |
| Output file: | Standard output |
Timofey wrote down all the natural numbers from 1 to n, converted each number to binary, and concatenated them together without spaces. As a result, he got a string like 110111001011101111000.... Your task is to determine how many groups of exactly two consecutive zeros are in this string.
The input consists of a single natural number n.
Output a single non-negative integer — the answer to the problem.
1 ≤ n ≤ 109
For example, when n = 18, the resulting binary string is: 1101110010111011110001001101010111100110111101111100001000110010. In this string, four suitable groups of two consecutive zeros are found.
| No. | Standard input | Standard output |
|---|---|---|
| 1 | |
|