Codeforces Round 833 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

bitmasks

chinese remainder theorem

combinatorics

constructive algorithms

math

number theory

*2100

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. ConstructOR

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou are given three integers $$$a$$$, $$$b$$$, and $$$d$$$. Your task is to find any integer $$$x$$$ which satisfies all of the following conditions, or determine that no such integers exist:

- $$$0 \le x \lt 2^{60}$$$;
- $$$a|x$$$ is divisible by $$$d$$$;
- $$$b|x$$$ is divisible by $$$d$$$.

Here, $$$|$$$ denotes the bitwise OR operation.

Input

Each test contains multiple test cases. The first line of input contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

Each test case consists of one line, containing three integers $$$a$$$, $$$b$$$, and $$$d$$$ ($$$1 \le a,b,d \lt 2^{30}$$$).

Output

For each test case print one integer. If there exists an integer $$$x$$$ which satisfies all of the conditions from the statement, print $$$x$$$. Otherwise, print $$$-1$$$.

If there are multiple solutions, you may print any of them.

Example

Input

812 39 56 8 14100 200 2003 4 62 2 218 27 3420 666 69987654321 123456789 999999999

Output

18 14 -1 -1 0 11 25599 184470016815529983

Note

In the first test case, $$$x=18$$$ is one of the possible solutions, since $$$39|18=55$$$ and $$$12|18=30$$$, both of which are multiples of $$$d=5$$$.

In the second test case, $$$x=14$$$ is one of the possible solutions, since $$$8|14=6|14=14$$$, which is a multiple of $$$d=14$$$.

In the third and fourth test cases, we can show that there are no solutions.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/08/2023 12:16:34 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|