众所周知，度度熊喜欢的字符只有两个：B和D。

今天，它发明了一种用B和D组成字符串的规则：

S(1)=B

S(2)=BBD

S(3)=BBDBBDD

…

S(n)=S(n−1)+B+reverse(flip(S(n−1))

其中，reverse(s)指将字符串翻转，比如reverse(BBD)=DBB，flip(s)指将字符串中的B替换为D，D替换为B，比如flip(BBD)=DDB。

虽然度度熊平常只用它的电脑玩连连看，这丝毫不妨碍这台机器无与伦比的运算速度，目前它已经算出了S(21000)的内容，但度度熊毕竟只是只熊，一次读不完这么长的字符串。它现在想知道，这个字符串的第L位（从1开始）到第R位，含有的B的个数是多少？

Input

第一行一个整数T，表示T(1≤T≤1000) 组数据。

每组数据包含两个数L和R(1≤L≤R≤1018) 。

Output

对于每组数据，输出S(21000)表示的字符串的第L位到第R位中B的个数。

Sample Input

3

1 3

1 7

4 8

Sample Output

2

4

3

把求l到r的变成，1到r减1到l，只要知道1到x又多少就可以了，如果恰好是2^{k-1，那么就是2}(k-1)，如果不是，就分成两部分左边是2^{(k-1)-1，右边是2}(k-1)到x，在根据是对称取反加一的变化求

#include<iostream>

#include<stdio.h>

#include<stdlib.h>

#include <iomanip>

#include<cmath>

#include<float.h>

#include<string.h>

#include<algorithm>

#define sf scanf

#define pf printf

#define sca(x) scanf("%d",&x)

#define mm(x,b) memset((x),(b),sizeof(x))

#include<vector>

#include<queue>

#include<map>

#define rep(i,a,n) for (int i=a;i<n;i++)

#define per(i,a,n) for (int i=a;i>=n;i--)

typedef long long ll;

const ll mod=1e9+100;

const double eps=1e-8;

using namespace std;

const double pi=acos(-1.0);

const int inf=0xfffffff;

const int N=1005;

ll num[65];

ll calc(ll x)

{

	if(x==0) return 0;

	if(x==1) return 1;

	if(x==2||x==3) return 2;

	ll i=0;

	while(i<x) i=i*2+1;

	i=(i-1)/2;

	return x-i+calc(i*2+1-x);

}

void first()

{

	int x=1;

	rep(i,1,61)

	{

		x*=2;

		num[i]=x-1;

	}

}

int main()

{

	ll re,l,r;

	first();

	cin>>re;

	while(re--)

	{

		cin>>l>>r;

		cout<<calc(r)-calc(l-1)<<endl;

	}

	return 0;

}