/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 500 点
問題文
円周上に N 個の椅子が並べられています。そのうち 1 つは玉座です。
高橋君は最初、玉座から時計回りに数えて 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
入力
入力は以下の形式で標準入力から与えられる。1 行目は以下の通りである。
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
1 つ目のテストケースでは、椅子が 10 個あり、高橋君は最初、玉座から時計回りに数えて 4 個隣の席に座っています。 時計回りに 3 個隣の席に移動する行動を 2 回行うと玉座に座れます。
2 つ目のテストケースでは、高橋君が玉座に座ることは永遠にできないので、-1 を出力します。
Score : 500 points
Problem Statement
We have N chairs arranged in a circle, one of which is a throne.
Takahashi is initially sitting on the chair that is S chairs away from the throne in the clockwise direction. Now, he will repeat the move below.
Move: Go to the chair that is K chairs away from the chair he is currently sitting on in the clockwise direction.
After how many moves will he be sitting on the throne for the first time? If he is never going to sit on it, report -1 instead.
You are asked to solve T test cases.
Constraints
- 1\leq T \leq 100
- 2\leq N \leq 10^9
- 1\leq S < N
- 1\leq K \leq 10^9
Input
Input is given from Standard Input in the following format. The first line is in the format below:
T
Then, the following T lines represent T test cases. Each of these lines is in the format below:
N S K
Output
For each test case, print the answer in its own line.
Sample Input 1
4 10 4 3 1000 11 2 998244353 897581057 595591169 10000 6 14
Sample Output 1
2 -1 249561088 3571
In the first test case, we have 10 chairs, and Takahashi is initially sitting on the chair that is 4 chairs away from the throne in the clockwise direction. He will be sitting on the throne after 2 moves of moving 3 chairs in the clockwise direction.
In the second test case, he will never sit on the throne, so we should print -1.