题目内容

给定三个非负整数 $X, Y, Z$。你可以任意选择一个非负整数 $k$，由此构造整数 $S = Y + Z \times k$。你的目标是使 $X$ 与 $S$ 的按位异或值 $X \oplus S$ 尽可能小。

请你求出在所有可行的 $k$ 下所能达到的最小异或结果。

约束：测试数据组数 $T$ 不超过 $10^4$。所有整数 $X, Y, Z$ 均满足 $0 \le X, Y, Z \le 10^{18}$。

输入描述

第一行输入一个整数 $T$（$1 \le T \le 10^4$），表示数据组数。接下来 $T$ 行，每行包含三个整数 $X, Y, Z$，用空格分隔，依次表示目标值、基础值和增量。

输出描述

对于每组测试数据，输出一行一个整数，表示能够达到的最小异或值。

样例1

输入

1
3 7 0

输出

4

说明

$Z=0$ 时，$S$ 只能为 $Y = 7$。$X \oplus S = 3 \oplus 7 = 4$。

样例2

输入

1
15 8 3

输出

1

说明

$Y=8$, $Z=3$，所有可行 $S$ 满足 $S \equiv 8 \equiv 2 \pmod 3$ 且 $S \ge 8$。可行序列为 $8, 11, 14, 17, 20, \dots$ 在 $X=15$ 附近的两个可行值为 14（不超过 15 的最大值）和 17（大于 15 的最小值）。计算 $15 \oplus 14 = 1$，$15 \oplus 17 = 30$。最小值为 1。

样例3

输入

1
3 5 8

输出

6

说明

$Y=5$, $Z=8$，由于 $k \ge 0$，可行 $S$ 均满足 $S \equiv 5 \pmod 8$，且最小值为 $S = 5$。$X = 3$ 小于该最小值，故只能选择 $S = 5$，得到 $3 \oplus 5 = 6$。若尝试更大的 $S$（如 $13$），异或结果更大。因此最小异或值为 6。