Count Numbers with Binary Substring 101

Given two integers low and high, return how many integers x with low <= x <= high have a binary representation that contains "101" as a contiguous substring.

The binary representation is written without leading zeros. For example, 5 is "101" and 10 is "1010"; both contain "101".

Examples

Example 1

Input: low = 1, high = 10
Output: 2
Explanation: 5 ("101") and 10 ("1010") contain "101"; no other value in [1, 10] does.

Example 2

Input: low = 6, high = 9
Output: 0
Explanation: None of "110", "111", "1000", "1001" contains "101".

Example 3

Input: low = 5, high = 5
Output: 1