题目描述

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

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

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

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

输入格式

入力は以下の形式で標準入力から与えられる。ここで、$\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$ 番目のテストケースに対する答えを出力せよ。

题目大意

有 $n$ 个排成一个环的格子，编号为 $0\sim n-1$。现在进行如下操作：

• 选择 $0$ 号格子，将其打上标记。
• 选择 $d$ 个格子后的第一个尚未被标记的格子，将其打上标记。
• 重复执行直到所有格子都被打上标记。

你需要输出第 $k$ 次标记的格子的编号。

共 $T$ 组数据。$1\le T\le 10^5$，$1\le k\le n\le10^9$，$1\le d\le 10^9$。

—— by Register_int

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

0
2
1
3
0
3
1
4
2

提示

制約

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

Sample Explanation 1

$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$ は印がついていないので、印をつける。