当前没有测试数据。

D - 标记

得分: $400$ 分

问题描述

有 $N$ 个编号为 $0$ 到 $N-1$ 的方块排列成一行。 Snuke 将按照以下步骤标记每个方块。

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

找出在第 $K$ 次时 Snuke 标记的方块的索引。

给定 $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$ 个测试用例的答案。

---

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

如果 $N=4$ 并且 $D=2$，Snuke 的标记过程如下。

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$ 未被标记，标记它。