配点 : $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$

出力

各テストケースに対し、答えを出力せよ。テストケースごとに改行すること。

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

2
-1
249561088
3571

$1$ つ目のテストケースでは、椅子が $10$ 個あり、高橋君は最初、玉座から時計回りに数えて $4$ 個隣の席に座っています。 時計回りに $3$ 個隣の席に移動する行動を $2$ 回行うと玉座に座れます。

$2$ つ目のテストケースでは、高橋君が玉座に座ることは永遠にできないので、-1 を出力します。