Nice Numbers

Time limit2sMemory limit128 MB

Summary

Count integers in the range [L, R] whose binary representation has three consecutive equal bits, using digit DP over bits.

Level: Medium6 of 10
Topics: Dynamic programming, Bit manipulation, Math
Solved: No attempts yet

Problem

A nonnegative integer is called a nice number if, in its binary representation, the same digit 0 or 1 appears at least three times consecutively. For example, 8 is 1000 in binary and 15 is 1111 in binary, so both are nice numbers. On the other hand, 27 is 11011 in binary, so it is not a nice number.

Given two integers L and R, determine how many nice numbers are between L and R, inclusive.

Input

The first line contains two integers L and R.

0 <= L <= R <= 2147483647

Output

Print the number of nice numbers between L and R, inclusive.

Examples4

Example 1
Input
```
17 100
```
Expected output
```
49
```
Example 2
Input
```
0 16
```
Expected output
```
5
```
Example 3
Input
```
2000000000 2100000000
```
Expected output
```
100000001
```
Example 4
Input
```
2 6
```
Expected output
```
0
```