← 返回题目列表

Codeforces · 1748/D

D. 构造OR

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

给你三个整数 $$$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$$$ 的倍数。

在第三个和第四个测试用例中,我们可以证明没有解决方案。