Problem L. Lines With Zeros ≡

Statement

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.

Input format

The input consists of a single natural number n.

Output format

Output a single non-negative integer — the answer to the problem.

Constraints

1 ≤ n ≤ 10⁹

Example explanation

For example, when n = 18, the resulting binary string is: 1101110010111011110001001101010111100110111101111100001000110010. In this string, four suitable groups of two consecutive zeros are found.

Sample tests

18

4