位运算

时间限制：1000 ms 内存限制：256 MiB

题目描述

令 $\text{lowbit}(x)$ 表示 $x$ 在二进制下 $1$ 的最低位（从 $0$ 开始计算），例如 $\text{lowbit}((1)_{10})=\text{lowbit}((1)_2)=0$，$\text{lowbit}((10)_{10})=\text{lowbit}((1010)_2)=1$，$\text{lowbit}((32)_{10})=\text{lowbit}((100000)_2)=5$，$\text{lowbit}((100)_{10})=\text{lowbit}((1100100)_2)=2$。

$T$ 次询问区间 $[l,r]$ 中有多少个 $i(l\le i\le r)$ 满足 $\text{lowbit}(i)<\text{lowbit}(i+1)$。

输入格式

第一行一个正整数 $T$。

接下来 $T$ 行，每行两个正整数，表示 $[l,r]$。

输出格式

共 $T$ 行，每行一个整数，表示答案。

样例

输入 #1

10
1 1
2 5
2 6
3 7
3 8
4 16
123 456
114514 1919810
114514 19198108933643
998244353 1000000007

输出 #1

1
2
2
3
3
6
167
902648
9599054409565
877828

数据范围

对于 $40\%$ 的数据，保证 $T\le 5\times 10^3$，$r-l\le 10^3$。

对于另外 $10\%$ 的数据，保证其与样例数据完全一致。

对于另外 $10\%$ 的数据，保证 $l=r$。

对于 $100\%$ 的数据，保证 $1\le T\le 10^5$，$1\le l\le r\le 10^{18}$。