依久依久

题号：NC229191
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

传说中，小喵和小矣是一对夫妻，他们关系很和洽。由于两位都是数学系毕业的，所以平日里他们经常一起研究数学。

最近，他们发现，一个数不仅可以被若干个不同的二进制分解，还可以被若干个斐波那契数分解！
这里定义 $fib_1=1,fib_2=2$ ，对于 $n\ge 3$ 有 $fib_n=fib_{n-1}+fib_{n-2}$ 。
但很快，他们发现分解方式并不唯一，不过只要满足分解成的斐波那契数不相邻，那么就有了唯一分解。形式化地。设 $x=\sum\limits_{i=1}^{k}fib_{a_i}$ ，满足 $\forall i \in[1,k),a_i+1<a_{i+1}$ ，则此为 ${x}$ 的唯一分解。
例如 ${x=6}$ ，那么 $x=fib_4+fib_1$ ，因此 $\text{val}(x)=fib_4 \oplus fib_1=4$ 。
小喵定义 $\text{val}(x)$ 表示 $\oplus_{i=1}^{k}fib_{a_i}$ ，即分解的斐波那契数的异或和。
小矣紧接着想知道，如果给定 ${l,r}$ ，那么 $\oplus_{i=l}^{r}f(i)$ 的值是多少呢？

由于小矣脑子里有许多疑惑，所以他会询问你很多次。

本场比赛大样例：https://uploadfiles.nowcoder.com/files/20211016/%E5%A4%A7%E6%A0%B7%E4%BE%8B.zip

输入描述:

第一行，输入查询组数 。
接下来  行，每行输入两个数  。

输出描述:

输出共  行，每行输出相应的异或和。

示例1

输入

复制

3
20 30
114 514
114514 1919810

输出

复制

15
142
792192

说明

对于第一组询问，从  的  值依次是  ，异或和为 。

备注:

对于所有数据，数据组数均满足 。
对于  的数据，；
对于  的数据，；
对于另外  的数据，；
对于  的数据，；
对于  的数据，。