F. K-hour Clock
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A "$$$k$$$-hour clock" is a day keeping method which follows the rules below:

  • A day is divided into $$$k$$$ hours, where the $$$i$$$-th hour is called the $$$(i-1)$$$ o' clock;
  • If it's $$$x$$$ o'clock now, it will be $$$(x+1)$$$ o'clock after $$$1$$$ hour if $$$0 \le x \lt k - 1$$$;
  • If it's $$$(k - 1)$$$ o'clock now, it will be $$$0$$$ o'clock after $$$1$$$ hour.

We know that it's $$$x$$$ o'clock now, and after $$$y$$$ hours it will be $$$z$$$ o'clock. What's the value of $$$k$$$?

Input

There are multiple test cases. The first line of the input is an integer $$$T$$$ (about $$$10^5$$$), indicating the number of test cases. For each test case:

The first and only line contains three integers $$$x$$$, $$$y$$$ and $$$z$$$ ($$$0 \le x, z \le 10^9$$$, $$$1 \le y \le 10^9$$$).

Output

For each test case output one line containing one integer, indicating the value of $$$k$$$. Note that there must be $$$1 \le k \le 2 \times 10^9$$$. If there are multiple valid answers, you can print any of them; If there is no valid answer, print "-1" (without quotes) instead.

Example
Input
4
11 18 5
3 49 4
1 9 1
1 3 10
Output
12
24
3
-1