给定整数 $$$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$$$ 时达到最小值。