Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 4131
K-hour Clock

Time Limit: 1 Second      Memory Limit: 65536 KB      Special Judge

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 < 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.

Sample Input

4
11 18 5
3 49 4
1 9 1
1 3 10

Sample Output

12
24
3
-1

Author: WENG, Caizhi
Source: The 2019 ICPC China Shaanxi Provincial Programming Contest
Submit    Status