2031: 无限序列

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：53 Solved：11

Description

 

我们按以下方式产生序列：

1、 开始时序列是： "1" ；

2、 每一次变化把序列中的 "1" 变成 "10" ，"0" 变成 "1"。
经过无限次变化，我们得到序列"1011010110110101101..."。
总共有 Q 个询问，每次询问为：在区间A和B之间有多少个1。

       请你写一个程序回答Q个询问

Input

第一行为一个整数Q，后面有Q行，每行两个数用空格隔开的整数a, b。

Output

共Q行，每行一个回答.


[数据范围]   1 <= Q <= 5000      1 <= a <= b < 263

Sample Input Copy 

1
2 8

Sample Output Copy 

4

HINT