Background

[An image should be here.]

Problem Description

We define $f(x)$ as the position of the lowest $1$ in the binary representation of $x$ (note that the lowest bit in binary is bit $0$). The following is the code in C++ (without considering issues caused by data types):

int f(int x){
	int ans = 0;
	while (x % 2 == 0){
		x /= 2;
		ans += 1;
	}
	return ans;
}

There are $T$ queries. For each query, given an interval $[l,r]$, find how many integers $i\in [l,r]$ satisfy $f(i)< f(i+1)$.

Input Format

The first line contains a positive integer $T$.
The next $T$ lines each contain two positive integers $l,r$, representing one query.

Output Format

Output $T$ lines, each containing one integer, the answer.

2
3 5
15 20

2
3

Hint

Constraints

This problem uses bundled testdata.

For $100\%$ of the testdata, $1\le T\le 10^5$, $1\le l\le r\le 10^{18}$.

Translated by ChatGPT 5