题目描述

有 $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$。

输入格式

按照下面形式输入

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

每行具体：

$N$ $D$ $K$

输出格式

你需要输出$T$行

对于第$i\ (1\leq\ i\ \leq\ T)$行、输出一个数表示答案

样例 #1

样例输入 #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

提示

制約

• $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$ -nd iteration) 放出 $x=(2+2)\bmod 4=0$ 。因为方格 $0$ 有标记，所以让 $x=(0+1)\bmod 4=1$ 。因为 $1$ 没有标记，所以标记它。 第 $3$ 次迭代）让 $x=(1+2)\bmod 4=3$ .因为方格 $3$ 没有标记，所以标记它。