Description

一个 $k$ 小时制的时钟是一种计时方法，遵循以下规则：

• 一天被分为 $k$ 小时，其中第 $i$ 小时称为 $(i-1)$ 点；
• 如果现在是 $x$ 点，那么在 $1$ 小时后将是 $(x+1)$ 点，前提是 $0 \le x < k - 1$；
• 如果现在是 $(k - 1)$ 点，那么在 $1$ 小时后将是 $0$ 点。

我们知道现在是 $x$ 点，经过 $y$ 小时后将是 $z$ 点。求 $k$ 的值。

Input Format

有多个测试用例。输入的第一行是一个整数 $T$（约 $10^5$），表示测试用例的数量。对于每个测试用例：

第一行包含三个整数 $x$、$y$ 和 $z$（$0 \le x, z \le 10^9$，$1 \le y \le 10^9$）。

Output Format

对于每个测试用例输出一行，包含一个整数，表示 $k$ 的值。注意必须有 $1 \le k \le 2 \times 10^9$。如果有多个有效答案，可以输出其中任意一个；如果没有有效答案，则输出 “-1”（不带引号）。

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

12
24
3
-1

Hint

题面翻译由 ChatGPT-4o 提供。