题目描述

有N个方块，索引从0到(N-1)，排列成一行。Snuke将按照以下步骤标记每个方块。

1. 标记方块0。
2. 重复以下步骤i - iii (N-1)次。
   1. 将变量x初始化为(A+D) mod N，其中A是上次标记的方块的索引。
   2. 当方块x被标记时，重复将x替换为(x+1) mod N。
   3. 标记方块x。

找出Snuke第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$，Snuke标记方块如下所示。

1. 标记方块0。
2. （第一次迭代）令$x=(0+2)\mod 4=2$。由于方块2没有被标记，将其标记。
   （第二次迭代）令$x=(2+2)\mod 4=0$。由于方块0已经被标记，令$x=(0+1)\mod 4=1$。由于方块1没有被标记，将其标记。
   （第三次迭代）令$x=(1+2)\mod 4=3$。由于方块3没有被标记，将其标记。