No testdata at current.

题目描述

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

1. 开始时序列是： 1 ；
2. 每一次变化把序列中的 1 变成 10 ，0 变成 1。

经过无限次变化，我们得到序列 1011010110110101101 ...。

总共有$Q$个询问，每次询问为：在区间$a$和$b$之间有多少个 1。

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

输入格式

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

输出格式

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

样例

样例输入

1
2 8

样例输出

4

数据范围与提示

对于$100\%$的数据, $1\leq Q\leq5000$，$1< a < b <2^{63}$