3705: 依久依久(第七轮03)
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：6
解决：2
题目描述
传说中，小喵和小矣是一对夫妻，他们关系很和洽。由于两位都是数学系毕业的， 所以平日里他们经常一起研究数学。
最近，他们发现，一个数不仅可以被若干个不同的二进制分解，还可以被若干个 斐波那契数分解！
这里定义fib1 = 1, fib2 = 2，对于n ≥ 3有 fibn = fibn−1 + fibn−2 。
但很快，他们发现分解方式并不唯一，不过只要满足分解成的斐波那契数不相邻，
由于小矣脑子里有许多疑惑，所以他会询问你很多次。
本场比赛大样例 ：
https://uploadfiles.nowcoder.com/files/20211016/%E5%A4%A7%E6%A0%B7%E4%BE %8B.zip
输入
第一行，输入查询组数T。
接下来T行，每行输入两个数l, r。
输出
输出共T行，每行输出相应的异或和。
样例输入 复制
3
20 30
114 514
114514 1919810样例输出 复制
15
142
792192提示
【样例 1 说明】
对于第一组询问，从x = 20 ∼ 30的val值依次是 10,21,20,23,22 ,23,16,17,18,29,28， 异或和为 15。
【数据范围】
对于所有数据，数据组数均满足 1 ≤ T ≤ 5 × 10^4 。
对于 10% 的数据， 1 ≤ l ≤ r ≤ 5000；
对于 30% 的数据， 1 ≤ l ≤ r ≤ 10^7；
对于另外 30% 的数据， 1 ≤ r − l + 1 ≤ 10^5；
对于 80% 的数据， 1 ≤ l ≤ r ≤ 10^9 ；
对于 100% 的数据， 1 ≤ l ≤ r ≤ 10^18 。