← 返回题目列表

Codeforces · 2180/E

E. 无效果异或

中文机器翻译题面 查看原题

丛林中,有一个湖,湖上长满了无限的睡莲叶。睡莲叶用非负整数 $$$0、1、2、3、\ldots$$$ 进行编号。编号在 $$$l$$$ 和 $$$r$$$(含)之间的睡莲称为 适合,而所有其他睡莲叶都不适合青蛙坐在上面。

目前,每个合适的睡莲叶上都栖息着一只青蛙。

奥斯塔德正在观察湖面,想要重新排列青蛙。为此,奥斯塔德可以选择一个正整数 $$$x$$$ 并将其告知青蛙。听到数字后,坐在第 $$$i$$$ 个睡莲叶上的青蛙会跳到第 $$$(i \oplus x)$$$ 个睡莲,其中 $$$\oplus$$$ 表示按位异或运算。

Ostad 喜欢青蛙,因此他想选择 $$$x$$$ 数字,使所有青蛙都位于合适的睡莲叶范围内。

通过计算 Ostad 可以选择多少个不同的数字 $$$x$$$ 来帮助 Ostad,这样青蛙就不会跳到睡莲叶的适当部分之外。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^5$$$)。测试用例的描述如下。

对于每个测试用例,有一行包含两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \leq l \leq r \leq 10^{15}$$$)。

输出

对于每个测试用例,输出一个整数,表示 $$$x$$$ 的有效值的数量。

示例

输入
复制

5
1 2
3 3
2 4
4 7
24189255811072 59373627899903

输出
复制

1
0
0
3
2199023255551

注意

在第一个测试用例中,$$$x = 3$$$ 是 Ostad 唯一可以选择的数字,如 $$$1 \oplus 3 = 2$$$ 和 $$$2 \oplus 3 = 1$$$,它们都在 $$$[1, 2]$$$ 范围内。

在第二个和第三个测试用例中,Ostad 没有有效的选择。对于第二种情况,由于我们需要 $$$x \gt 0$$$,因此我们唯一的青蛙将离开范围。类似地,在第三种情况下,不存在有效的 $$$x$$$ 来将青蛙保持在所需的范围内。

在第四个测试用例中,Ostad 可以选择 $$$1$$$、$$$2$$$ 或 $$$3$$$。

链接到可视化工具