题目描述

定义函数 $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$。

输出格式

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

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$。