题目描述

円周上に $N$ 個の椅子が並べられています。そのうち $1$ つは玉座です。

高橋君は最初、玉座から時計回りに数えて $S$ 個隣の椅子に座っており、次の行動を繰り返します。

行動：いま座っている椅子から時計回りに数えて $K$ 個隣の椅子に移動し座る。

高橋君がはじめて玉座に座ることができるのは何回目の行動の後ですか？ ただし、玉座に座ることが永遠にできない場合は、代わりに -1 を出力してください。

$T$ 個のテストケースに答えてください。

输入格式

入力は以下の形式で標準入力から与えられる。$1$ 行目は以下の通りである。

$T$

そして、続く $T$ 行が $T$ 個のテストケースを表す。これらはそれぞれ以下の形式の行である。

$N$ $S$ $K$

输出格式

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

题目大意

有 $N$ 把椅子围成一圈，编号为 $1$ 至 $N$。你一开始坐在编号为 $S+1$ 的椅子上。

一次操作为往右移动 $K$ 次位置。求经过多少次操作能够到达编号为 $1$ 的椅子。不能到达输出 -1。

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$

Sample Explanation 1

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