是的，这个游戏又来了。Nim 游戏是一种数学策略游戏，两名玩家轮流从不同的堆中移除物品。在每一轮中，玩家必须至少移除一个物品，并且可以从同一个堆中移除任意数量的物品。移除最后一个物品的玩家获胜。

在本题中，我们只使用 3 堆物品，且初始状态比较特殊，总是 $N, 2 \times N, 3 \times N$，其中 $N$ 是一个正整数。例如，如果 $N=3$，则 3 堆物品的初始数量分别为 3, 6 和 9。

必胜状态是指当前轮到行动的玩家拥有一种策略，无论对方如何操作，都能赢得游戏的状态。

在本题中，给定两个整数 $L$ 和 $R$，你的任务是找出有多少个不同的 $N$ 值（满足 $L \le N \le R$），使得如果我们使用 $N$ 作为上述初始状态，该状态对于先手玩家来说是一个必胜状态。

输入格式

程序将针对一个或多个测试用例进行测试。输入的第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试用例的数量。接下来是 $T$ 个测试用例。

每个测试用例仅包含一行，包含两个由空格分隔的整数 $L$ 和 $R$ ($1 \le L \le R \le 2^{61}$)，即上述描述的范围。

输出格式

对于每个测试用例，输出一行，表示满足上述条件的 $N$ 的不同值的数量。

样例

输入格式 1

2
1 5
10 1000

输出格式 1

1
854

说明

在第一个测试用例中，唯一能给出必胜状态的 $N$ 的值是 3，此时状态为 $(3, 6, 9)$。