1236. Non-Negative Integers without Consecutive Ones

Given an integer n, count the integers in the range [0, n] whose binary representation contains no two consecutive ones. The input is JSON {n}.

Input: JSON {n}.

Output: Integer — the count of such integers.

Examples

Example 1

Input: {"n":5}
Output: 5
Explanation: 0, 1, 2, 4, 5 qualify.

Example 2

Input: {"n":1}
Output: 2
Explanation: 0 and 1.

Example 3

Input: {"n":2}
Output: 3
Explanation: 0, 1, 2.