D. ConstructOR
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны три целых числа $$$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$$$.

Если существует несколько решений, выведите любое из них.

Пример
Входные данные
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
Выходные данные
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$$$.

Можно показать, что в третьем и четвёртом наборах входных данных решений не существует.