Throne

题目描述

我们有 $N$ 把椅子按圆排列，其中一把是宝座。 Takahashi 最初坐在距离宝座顺时针方向 $S$ 把椅子的位置上。现在，他将重复下面的移动。 移动：从当前所坐的椅子出发，顺时针方向移动 $K$ 把椅子，去到那把椅子上。 经过多少次移动他会第一次坐在宝座上？如果他永远不会坐到宝座上，则输出 $-1$。 你需要解 $T$ 个测试用例。

输入格式

输入由标准输入给出，格式如下。第一行是下面的格式： $T$

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

输出格式

对于每个测试用例，各自单独一行输出答案。

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

2
-1
249561088
3571

提示

$1\leq T \leq 100$ $2\leq N \leq 10^9$ 1\leq S < N $1\leq K \leq 10^9$在第一个测试用例中，我们有 $10$ 把椅子，Takahashi 最初坐在距离宝座顺时针方向 $4$ 把椅子的位置上。 他每次顺时针移动 $3$ 把椅子，经过 $2$ 次移动后会坐到宝座上。 在第二个测试用例中，他永远不会坐到宝座上，因此我们应该输出 $-1$。

标签: AtCoder|abc186E

来源

AtCoder|abc186E