C. 异或距离

时间限制：每个测试 $2$ 秒
内存限制：每个测试 $256$ MB

给定整数 $a$、$b$、$r$。对于所有满足 $0 \le x \le r$ 的 $x$，求 $|(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}$）。

输出
对于每个测试用例，输出一个数——可能达到的最小值。

样例
输入

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

输出

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$ 时取得。