题目描述

定义函数 $f(x)$ 如下：

$$\begin{cases} f(1) = a \\ f(2) = b \\ f(x) = f(x - 1) \oplus f(x - 2) \end{cases} $$

这里的 $x \oplus y$ 表示整数 $x$ 和 $y$ 的按位异或运算。

现在给定四个整数 $a$、$b$、$l$、$r$，你的任务是计算 从 $l$ 到 $r$（包含两端）每个整数对应的函数值之和。

更正式地表示为：

$$\left( \sum_{x=l}^{r} f(x) \right) = f(l) + f(l + 1) + \dots + f(r) $$

输入格式

第一行一个整数 $T$表示测试点数量。

接下来 $T$ 个测试点，每个测试点包含一行，四个整数 $a$、$b$、$l$、$r$。

输出格式

对于每个测试点，输出所求的和。

请注意！ 某些测试用例的答案可能超出 32 位整数范围，因此你应该在程序中使用至少 64 位整数类型（例如 C++ 中的 long long）。

可以证明，每个测试用例的答案不超过 $2 \cdot 10^{18}$。

4
1 3 4 6
2 10 11 20
100 20 33 34
10 2 3 5

6
70
212
20

数据范围

• 对于 $30\%$ 的数据，$l=r$。
• 对于另外 $30\%$ 的数据，$\sum r-l+1 \le 5\times 10^5$。
• 对于 $100$ 的数据，没有额外限制，$1 \le T \le 10^4$，$1 \le a, b \le 10^9$，$1 \le l \le r \le 10^9$。