E - 宝座

得分：$500$分

问题描述

我们有$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$组测试用例。每行表示一个测试用例，格式如下。

输出

对于每组测试用例，输出一个单独的行表示答案。

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

2
-1
249561088
3571

在第一个测试用例中，有$10$个座位，高桥最初坐在距离宝座顺时针方向$4$个座位的椅子上。 他需要顺时针方向移动$3$个座位，经过$2$次移动后，他将坐到宝座上。

在第二个测试用例中，他永远不会坐在宝座上，因此输出-1。