Problem Description

Count how many numbers between 1 and N (inclusive) have equal number of 0s and 1s in their binary representation (without leading zeros).

Input Format

A single integer N.

Output Format

Count of numbers with equal 0s and 1s in binary representation.

Constraints

• 1 ≤ N ≤ 10^6

• Consider binary representation without leading zeros

• Count 0s and 1s in each number's binary form

• Include only numbers where count of 0s equals count of 1s

• Example: 6 (binary 110) has 1 zero and 2 ones, not equal

Sample Input/Output

10

2

Explanation

Numbers 1-10 in binary: 1(1), 2(10), 3(11), 4(100), 5(101), 6(110), 7(111), 8(1000), 9(1001), 10(1010). Equal 0s and 1s: 6(110) has 1 zero, 2 ones - not equal. Actually, let me recheck: 9(1001) has 2 zeros, 2 ones - equal. 10(1010) has 2 zeros, 2 ones - equal. So answer is 2.