一个很长的二进制字符串通过如下过程生成：

1. 初始字符串为 1。
2. 每过一秒，将当前字符串中的每一个 1 替换为 10，将每一个 0 替换为 1。

字符串在最初几秒的状态如下：$1, 10, 101, 10110, 10110101$。

设经过 $10^{100}$ 秒后得到的字符串为 $s$。你需要回答 $Q$ 个询问，每个询问形式如下：在字符串 $s$ 中，第 $l$ 个字符到第 $r$ 个字符（包含端点）之间有多少个 1？

输入格式

第一行包含一个整数 $Q$ ($1 \le Q \le 300,000$)，表示询问的数量。

接下来 $Q$ 行，每行包含两个用空格分隔的整数 $l, r$ ($1 \le l \le r \le 10^{18}$)，表示一次询问。

输出格式

对于每个询问，输出字符串 $s$ 中第 $l$ 个字符到第 $r$ 个字符（包含端点）之间 1 的数量。

样例数据

输入

3
3 9
6 6
1 12

输出

5
1
8

说明

可以证明，该字符串的前 $12$ 个字符为 $101101011011$。

对于第一个询问，第 $3$ 个字符到第 $9$ 个字符之间共有 $5$ 个 1，对应的子串为 $1101011$。

对于第二个询问，第 $6$ 个字符到第 $6$ 个字符之间共有 $1$ 个 1，对应的子串为 $1$。

对于第三个询问，第 $1$ 个字符到第 $12$ 个字符之间共有 $8$ 个 1，对应的子串为 $101101011011$。

子任务

子任务 1（7 分）

$Q = 1$，$r \le 300,000$

子任务 2（10 分）

$l = 1$，$r \le 300,000$

子任务 3（13 分）

$r \le 300,000$

子任务 4（20 分）

$l = 1$，且 $r$ 等于经过某个整数秒后字符串的长度

子任务 5（15 分）

$l = r$

子任务 6（15 分）

$Q = 1$

子任务 7（10 分）

$r \le 10^9$

子任务 8（10 分）

无额外限制