标记

题目描述

有 $N$ 个方块,编号为 $0$ 到 $(N-1)$,排成一行。 Snuke 将按以下步骤标记所有方块。

1. 标记方块 $0$。
2. 重复以下步骤 i ~ iii 共 $(N-1)$ 次:
   • i. 用变量 $x$ 初始化为 $(A+D) \bmod N$,其中 $A$ 是上一次标记的方块编号。
   • ii. 当方块 $x$ 已被标记时,反复将 $x$ 替换为 $(x+1) \bmod N$。
   • iii. 标记方块 $x$。

求 Snuke 第 $K$ 次标记的方块编号。

给定 $T$ 个测试用例,分别求出每个测试用例的答案。

输入格式

输入按以下格式从标准输入给出,其中 $\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 按以下方式标记方块。

标记方块 $0$。

(第 $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$ 未被标记,标记它。

数据范围

• 输入中的所有值均为整数。
• $1\leq T \leq 10^5$
• $1\leq K\leq N \leq 10^9$
• $1\leq D \leq 10^9$