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 翻译