[Solution] ConstructOR Codeforces Solution

D. ConstructOR

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You 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≤𝑥<260$0\le x<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≤𝑡≤104$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≤𝑎,𝑏,𝑑<230$1\le a,b,d<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$-1$.

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

Note

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

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

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