著名的 Thue-Morse 序列 $T = t_0t_1t_2 \dots$ 是一个无限二进制序列，定义如下：如果 $n$ 的二进制表示中 1 的个数为奇数，则 $t_n = 1$，否则 $t_n = 0$。

该序列以 $01101001100101101001011001101001 \dots$ 开头。

考虑该序列的一个子串 $t_{l..r} = t_l t_{l+1} \dots t_r$。求 $t_{l..r}$ 在 $T$ 中第一次出现的位置。换句话说，求最小的非负整数 $i$，使得 $t_{l..r} = t_{i..i+(r-l)}$。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^5$)。

接下来是各测试用例的描述。

每个测试用例仅一行，包含两个整数 $l$ 和 $r$ ($0 \le l \le r \le 10^{18}$)。

输出格式

对于每个测试用例，输出 $t_{l..r}$ 在 $T$ 中第一次出现的位置索引。

样例

样例输入 1

3
0 10
13 13
23 27

样例输出 1

0
1
5

说明

在第一个测试用例中，$t_{0..10}$ 显然在 $T$ 中第一次出现在索引 0 处。

在第二个测试用例中，$t_{13..13} = 1$ 在 $T$ 中第一次出现在索引 1 处。

在第三个测试用例中，$t_{23..27} = 00110$ 在 $T$ 中第一次出现在索引 5 处。