Description

小任非常喜欢一个数 $x$，但它具体是多少，已经被他忘记了，小任只能想起 $x\ mod\ a = b$，现在小任已经放弃寻找这个数了，但他还是想要知道 $x\ mod\ c$ 为多少。如果可以唯一确定 $x\ mod\ c$ 的值，那就输出 $x\ mod\ c$ 的值，否则，输出 $-1$。

$mod$ 表示取模运算，$a\ mod\ b$ 表示 $a$ 除以 $b$ 的余数。例如：$7\ mod\ 3 = 1$。

Format

Input

第一行有一个整数 $t (1\leq t\leq10^5)$，表示测试用例数。

接下来 $t$ 行，每行有三个正整数 $a，b，c\ (1 \leq a,c\leq10^9, 0 \leq b < 10^9, a > b)$，分别表示已知 $x\ mod\ a = b$，希望求 $x\ mod\ c$ 的值。

Output

输出 $t$ 行，每行输出一个整数，如果可以唯一确定 $x\ mod\ c$ 的值，那就输出 $x\ mod\ c$ 的值，否则，输出 $-1$。

Samples

2
6 3 3
5 3 2

0
-1

Limitation

1s, 1024KiB for each test case.