题目描述

对于一个数字$\red{x，}$我们定义$\red{f_x}$表示有多少个数字$\red{i(0<=i<=x)}$满足$\red{x\&i=0}$。

现在需要计算$\red{\sum_{i=l_j}^{r_j}{f_i}}$。

每一个数据点包含多组测试数据。

输入格式

第一行包含一个数字$\red{T，}$表示数据组数。

接下来$\red{T}$行，$\red{i+1}$行两个数字$\red{l_i，}$$\red{r_i，}$表示每一组测试数据。

输出格式

一共$\red{T}$行，第$\red{i}$行代表每第$\red{i}$组数据的答案。

样例

输入样例

5
1 2
3 5
2 4
4 6
7 8

输出样例

3
7
7
8
9

提示

样例说明

对于最后一组数据：$\red{f_7=1（}$即$\red{0）}$,$\red{f_8=8（}$即$\red{0,1,2,3,4,5,6,7）}$，所以它应该输出 $\red{9 }$。

数据范围

对于$\red{30\%}$的数据，保证：$\red{1<=\sum_{i=1}^{n}{(r_i-l_i)<=10^6}}$。

对于$\red{60\%}$的数据，保证：$\red{1<=\sum_{i=1}^{n}{(r_i-l_i)<=10^7}}$。

对于$\red{100\%}$的数据，保证：$\red{1<=T<=10^4，}$$\red{1<=l_i<=r_i<=2\times 10^7}$。

本题读入量较大，请使用较快读入方式。

对于这个问题的求和，需要使用前缀和才能顺利通过本题。