A16803. No Effect XOR
编程题
普及+/提高
知识点
题目描述
在丛林里，有一片湖泊，湖面上有无数个睡莲叶。每片睡莲叶都用非负整数编号 $0, 1, 2, 3, \ldots$。编号在 $l$ 到 $r$（包含两端）的睡莲叶被称为“合适”的睡莲叶，其他编号的睡莲叶都不适合青蛙停留。
目前，每一片合适的睡莲叶上都坐着一只青蛙。
Ostad 正在观察这片湖，并想要重新排列青蛙的位置。为此，Ostad 可以选择一个正整数 $x$ 并宣布给青蛙们。听到这个数字后，坐在第 $i$ 号睡莲叶上的青蛙会跳到第 $(i \oplus x)$ 号睡莲叶上，这里 $\oplus$ 表示[按位异或运算](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)。
Ostad 很喜欢这些青蛙，因此希望选择一个数字 $x$，使得所有青蛙跳跃之后仍然全部停留在合适睡莲叶区域内。
请你帮助 Ostad 计算，有多少个不同的 $x$ 可以被选择，使得没有青蛙跳出合适区间。
目前，每一片合适的睡莲叶上都坐着一只青蛙。
Ostad 正在观察这片湖，并想要重新排列青蛙的位置。为此，Ostad 可以选择一个正整数 $x$ 并宣布给青蛙们。听到这个数字后，坐在第 $i$ 号睡莲叶上的青蛙会跳到第 $(i \oplus x)$ 号睡莲叶上，这里 $\oplus$ 表示[按位异或运算](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)。
Ostad 很喜欢这些青蛙，因此希望选择一个数字 $x$，使得所有青蛙跳跃之后仍然全部停留在合适睡莲叶区域内。
请你帮助 Ostad 计算，有多少个不同的 $x$ 可以被选择，使得没有青蛙跳出合适区间。
输入格式
每个测试点包含多个测试用例。第一行为测试用例个数 $t$（$1 \leq t \le 10^5$）。接下来 $t$ 行，每行包含两个整数 $l$ 和 $r$（$1 \leq l \leq r \leq 10^{15}$）。
输出格式
对于每个测试用例，输出一个整数，表示有多少个有效的 $x$ 可以让所有青蛙都停留在合适区间。
输入输出样例
输入 #1
5 1 2 3 3 2 4 4 7 24189255811072 59373627899903
输出 #1
1 0 0 3 2199023255551
说明/提示
在第一个测试用例中，$x = 3$ 是唯一可以选择的数字，因为 $1 \oplus 3 = 2$，$2 \oplus 3 = 1$，都在区间 $[1, 2]$ 内。
对于第二和第三个测试用例，没有可选的合法 $x$。在第二个用例里，由于要求 $x > 0$，所以唯一的一只青蛙会跳出区间。同理，第三个用例也不存在可以使青蛙都在目标区间的 $x$。
在第四个测试用例中，Ostad 可以选择 $1$、$2$ 或 $3$。
[可视化工具链接](https://codeforces.com/assets/contests/2180/E_iwaheighoogh1ereef5A.html)
对于第二和第三个测试用例，没有可选的合法 $x$。在第二个用例里，由于要求 $x > 0$，所以唯一的一只青蛙会跳出区间。同理，第三个用例也不存在可以使青蛙都在目标区间的 $x$。
在第四个测试用例中，Ostad 可以选择 $1$、$2$ 或 $3$。
[可视化工具链接](https://codeforces.com/assets/contests/2180/E_iwaheighoogh1ereef5A.html)