产生01串

成绩 0 开启时间 2013年02月21日 星期四 23:02
折扣 0.8 折扣时间 2013年02月28日 星期四 23:02
允许迟交 是 关闭时间 2013年02月28日 星期四 23:02
输入文件 infinit.in 输出文件 infinit.out

【问题描述】

我们按以下方式产生序列：
1、 开始时序列是： " 1 " ；
2、 每一次变化把序列中的 " 1 " 变成 " 10 " ，" 0 " 变成 " 1 "。
经过无限次变化，我们得到序列" 1011010110110101101... "。
总共有 Q 个询问，每次询问为：在区间A和B之间有多少个1。

任务 写一个程序回答 Q个询问

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

输出 共 Q行，每行一个回答

约定

  • 1 <= Q <= 5000
  • 1 <= a <= b < 2^63

样例

infinit.in

infinit.out

1
2 8

4