该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定两个自然数 $l$ 和 $r$，请你计算：

$l \oplus (l+1)$ $\oplus (l+2) \oplus \cdots \oplus r$

其中，符号 $\oplus$ 表示按位异或运算。

由于区间范围可能很大，无法直接逐个枚举，请你设法在更优的时间复杂度内完成计算。

输入格式

第一行输入一个整数 $T(1\leq T\leq 10^5)$，表示查询的组数。

接下来 $T$ 行，每行输入两个整数 $l, r(0\leq l\leq r\leq 10^{18})$。

输出格式

对于每组查询，输出一行一个整数，表示从 $l$ 到 $r$ 的所有整数按位异或的结果。

输入输出样例 #1

输入 #1

3
2 4
0 7
5 5

输出 #1

5
0
5