配点 : 100 点
問題文
T 测试用例解决以下问题。
非負整数 L,R\,(L\leq R) 。 对于\lbrace L,L+1,\ldots,R\rbrace 的子集 1 有多少个整数可以作为集合中数字的总异或?然而,0 数字的异或为 0 。
异或定义
非負整数 x,y 的按位异或 x\operatorname{XOR}y 定义如下。- x\operatorname{XOR}y 该值应乘以 2 当用基本符号表示时 2^k 中的位数为x 和 按字典顺序比较 y 该值应乘以2 当用基本符号表示时 2^k 只有一位数字 如果 1 如果 1 如果没有 0。
制約
- 1\leq T\leq 2\times 10^5
- 0\leq L\leq R\lt 2^{60}
入力
输入是按以下格式从标准输入给出的。
T
\mathrm{test}_1
\mathrm{test}_2
\vdots
\mathrm{test}_T
在这里,\mathrm{test}_i 是 您也可以写 i 个测试用例的信息,并以以下格式给出:
L R
出力
请按顺序输出每个测试用例的答案,以换行符分隔。
对于每个测试用例,打印总异或的可能整数的数量。
入力例 1
3 8 10 2 2 123 456
出力例 1
8 2 512
1 我们来谈谈第三个测试用例。总异或的可能整数是 0,1,2,3,8,9,10,11 可以得到第 8 一。例如, 作为\lbrace 8,9,10\rbrace 的子集 如果您选择 \lbrace 8,10\rbrace ,则总异或将为 2 。