← 返回题目列表

AtCoder · abc186_e

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 测试用例。每行的格式如下:

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.