← 返回题目列表

Codeforces · 1918/C

C. 异或距离

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

给定整数 $$$a$$$、$$$b$$$、$$$r$$$。找出所有 $$$0 \leq x \leq r$$$ 中 $$$|({a \oplus x}) - ({b \oplus x})|$$$ 的最小值。

$$$\oplus$$$ 是按位异或运算,$$$|y|$$$ 是$$$y$$$ 的绝对值。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例包含整数 $$$a$$$、$$$b$$$、$$$r$$$ ($$$0 \le a, b, r \le 10^{18}$$$)。

输出

对于每个测试用例,输出一个数字 - 最小的可能值。

示例

输入 #1

10
4 6 0
0 3 2
9 6 10
92 256 23
165 839 201
1 14 5
2 7 2
96549 34359 13851
853686404475946 283666553522252166 127929199446003072
735268590557942972 916721749674600979 895150420120690183

输出 #1

2
1
1
164
542
5
3
37102
27934920819538516
104449824168870225

注意

在第一个测试中,当$$$r = 0$$$时,那么$$$x$$$肯定等于$$$0$$$,所以答案是$$$|{4 \oplus 0} - {6 \oplus 0}| = |4 - 6| = 2$$$。

在第二次测试中:

- 当 $$$x = 0$$$ 时,$$$|{0 \oplus 0} - {3 \oplus 0}| = |0 - 3| = 3$$$。
- 当 $$$x = 1$$$ 时,$$$|{0 \oplus 1} - {3 \oplus 1}| = |1 - 2| = 1$$$。
- 当 $$$x = 2$$$ 时,$$$|{0 \oplus 2} - {3 \oplus 2}| = |2 - 1| = 1$$$。

因此,答案是$$$1$$$。

在第三个测试中,当 $$$x = 1$$$ 时达到最小值。