2807: 无限序列
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：3
解决：3
题目描述
我们按以下方式产生序列：
1、开始时序列是： "1" ；
2、每一次变化把序列中的 "1" 变成 "10" ，"0" 变成 "1"。
经过无限次变化，我们得到序列"1011010110110101101..."。
总共有 Q 个询问，每次询问为：在区间A和B之间有多少个1。
任务:写一个程序回答Q个询问
输入
文件输入的第一行为一个整数Q，后面有Q行，每行两个数用空格隔开的整数a, b。
输出
文件输出共Q行，每行一个回答。
样例输入 复制
1
2 8样例输出 复制
4提示
1 <= Q <= 5000
1 <= a <= b < 2^63