AT_abc290_d [ABC290D] Marking

有 $N$ 个编号从 $0$ 到 $N-1$ 的格子排成一排。现在，すぬけくん将按照以下步骤依次在所有格子上做标记。 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$ 组测试数据，请分别输出每组的答案。

输入按以下格式从标准输入读入。这里，$\mathrm{test}_i$ 表示第 $i$ 个测试用例。 > $T$ > $\mathrm{test}_1$ > $\mathrm{test}_2$ > $\vdots$ > $\mathrm{test}_T$ 每个测试用例的输入格式如下： > $N$ $D$ $K$

输出共 $T$ 行。 第 $i$ 行输出第 $i$ 个测试用例的答案。

### 数据范围 - $1\leq T\leq 10^5$ - $1\leq K\leq N\leq 10^9$ - $1\leq D\leq 10^9$ - 所有输入均为整数 ### 样例解释 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$ 未被标记，做标记。 由 ChatGPT 4.1 翻译