問題文

$0$ から $N-1$ までの番号がつけられた $N$ 個のマスが並んでいます。 今から、すぬけくんが以下の手順に従って全てのマスに印をつけていきます。

1. マス $0$ に印をつける。
2. 次の i - iii の手順を $N−1$ 回繰り返す。
   1. 最後に印をつけたマスの番号を $A$ としたとき、変数 $x$ を $(A+D) \\bmod N$ で初期化する。
   2. マス $x$ に印が付いている限り、 $x$ を $(x+1) \\bmod N$ に更新することを繰り返す。
   3. マス $x$ に印をつける。

すぬけくんが $K$ 番目に印をつけるマスの番号を求めてください。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

• $1\\leq T \\leq 10^5$
• $1\\leq K\\leq N \\leq 10^9$
• $1\\leq D \\leq 10^9$
• 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。ここで、$\\mathrm{test}_i$ は $i$ 番目のテストケースを意味する。

$T$ $\\mathrm{test}_1$ $\\mathrm{test}_2$ $\\vdots$ $\\mathrm{test}_T$

各テストケースは以下の形式で与えられる。

$N$ $D$ $K$

出力

$T$ 行出力せよ。

$i\\ (1\\leq i \\leq T)$ 行目には、$i$ 番目のテストケースに対する答えを出力せよ。

入力例 1

9
4 2 1
4 2 2
4 2 3
4 2 4
5 8 1
5 8 2
5 8 3
5 8 4
5 8 5

出力例 1

0
2
1
3
0
3
1
4
2

$N=4,D=2$ のとき、すぬけくんは以下のように印をつけていきます。

1. マス $0$ に印をつける。
2. (1回目) $x=(0+2)\\bmod 4=2$ と初期化する。マス $2$ は印がついていないので、印をつける。
   (2回目) $x=(2+2)\\bmod 4=0$ と初期化する。マス $0$ は印がついているので、$x=(0+1)\\bmod 4=1$ と更新する。マス $1$ は印がついていないので、印をつける。
   (3回目) $x=(1+2)\\bmod 4=3$ と初期化する。マス $3$ は印がついていないので、印をつける。