“$k$ 小时时钟”是一种遵循以下规则的计时方法：

• 一天被分为 $k$ 个小时，其中第 $i$ 个小时被称为 $(i - 1)$ 点；
• 如果现在是 $x$ 点，经过 1 小时后将是 $(x + 1)$ 点（当 $0 \le x < k - 1$ 时）；
• 如果现在是 $(k - 1)$ 点，经过 1 小时后将是 $0$ 点。

已知现在是 $x$ 点，经过 $y$ 小时后将是 $z$ 点。请问 $k$ 的值是多少？

输入格式

输入包含多组测试数据。第一行是一个整数 $T$（约 $10^5$），表示测试数据的组数。对于每组测试数据：

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

输出格式

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

样例

样例输入 1

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

样例输出 1

12
24
3
-1