给你三个整数 $$$a$$$、$$$b$$$ 和 $$$d$$$。你的任务是找到满足以下所有条件的任意整数$$$x$$$,或者确定不存在这样的整数:
- $$$0 \le x \lt 2^{60}$$$;
- $$$a|x$$$ 可以被 $$$d$$$ 整除;
- $$$b|x$$$ 可以被 $$$d$$$ 整除。
这里,$$$|$$$ 表示按位或运算。
输入
每个测试包含多个测试用例。输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例由一行组成,包含三个整数 $$$a$$$、$$$b$$$ 和 $$$d$$$ ($$$1 \le a,b,d \lt 2^{30}$$$)。
输出
对于每个测试用例打印一个整数。如果存在满足语句中所有条件的整数 $$$x$$$,则打印 $$$x$$$。否则,打印$$$-1$$$。
如果有多个解决方案,您可以打印其中任何一个。
示例
输入 #1
8 12 39 5 6 8 14 100 200 200 3 4 6 2 2 2 18 27 3 420 666 69 987654321 123456789 999999999
输出 #1
18 14 -1 -1 0 11 25599 184470016815529983
注意
在第一个测试用例中,$$$x=18$$$ 是可能的解决方案之一,因为 $$$39|18=55$$$ 和 $$$12|18=30$$$ 都是 $$$d=5$$$ 的倍数。
在第二个测试用例中,$$$x=14$$$ 是可能的解决方案之一,因为 $$$8|14=6|14=14$$$ 是 $$$d=14$$$ 的倍数。
在第三个和第四个测试用例中,我们可以证明没有解决方案。