问题描述

我们有 $N$ 把椅子围成一个圆圈，其中一把是王座。

高桥最初坐在与王座顺时针方向相距 $S$ 把椅子的位置上。现在，他将重复以下移动。

移动：走到他当前位置顺时针方向上相距 $K$ 把椅子的位置上。

他第一次坐上王座需要多少次移动？如果他永远不会坐上去，请报告 -1。

您需要解决 $T$ 个测试用例。

约束条件

• $1\\leq T \\leq 100$
• $2\\leq N \\leq 10^9$
• $1\\leq S < N$
• $1\\leq K \\leq 10^9$

输入

输入以以下格式从标准输入给出。第一行是以下格式之一：

$T$

然后，接下来的 $T$ 行表示 $T$ 个测试用例。每行的格式如下：

$N$ $S$ $K$

输出

对于每个测试用例，在一行中打印答案。

示例输入 1

4
10 4 3
1000 11 2
998244353 897581057 595591169
10000 6 14

示例输出 1

2
-1
249561088
3571

在第一个测试用例中，我们有 $10$ 把椅子，高桥最初坐在与王座顺时针方向相距 $4$ 把椅子的位置上。他经过 $2$ 次移动，每次向顺时针方向移动 $3$ 把椅子，最后坐上了王座。

在第二个测试用例中，他永远也不会坐上王座，所以我们应该打印出 -1。