102903: [Atcoder]ABC290 D - Marking

Problem Statement

There are $N$ squares indexed $0$ through $(N-1)$ arranged in a line. Snuke is going to mark every square by the following procedure.

1. Mark square $0$.
2. Repeat the following steps i - iii $(N-1)$ times.
   1. Initialize a variable $x$ with $(A+D) \bmod N$, where $A$ is the index of the square marked last time.
   2. While square $x$ is marked, repeat replacing $x$ with $(x+1) \bmod N$.
   3. Mark square $x$.

Find the index of the square that Snuke marks for the $K$-th time.

Given $T$ test cases, find the answer for each of them.

Constraints

• $1\leq T \leq 10^5$
• $1\leq K\leq N \leq 10^9$
• $1\leq D \leq 10^9$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format, where $\mathrm{test}_i$ denotes the $i$-th test case:

$T$
$\mathrm{test}_1$
$\mathrm{test}_2$
$\vdots$
$\mathrm{test}_T$

Each test case is given in the following format:

$N$ $D$ $K$

Output

Print $T$ lines.

The $i$-th $(1\leq i \leq T)$ line should contain the answer to the $i$-th test case.

Sample Input 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

Sample Output 1

0
2
1
3
0
3
1
4
2

If $N=4$ and $D=2$, Snuke marks the squares as follows.

1. Mark square $0$.
2. ($1$-st iteration) Let $x=(0+2)\bmod 4=2$. Since square $2$ is not marked, mark it.
   ($2$-nd iteration) Let $x=(2+2)\bmod 4=0$. Since square $0$ is marked, let $x=(0+1)\bmod 4=1$. Since square $1$ is not marked, mark it.
   ($3$-rd iteration) Let $x=(1+2)\bmod 4=3$. Since square $3$ is not marked, mark it.

问题描述

有一行排列着编号为0到$(N-1)$的$N$个方格。Snuke将按照以下过程在每个方格上做标记。

1. 标记方格0。
2. 重复以下步骤i-iii $(N-1)$次。
   1. 将变量$x$初始化为$(A+D) \bmod N$，其中$A$是上一次标记的方格的索引。
   2. 当方格$x$被标记时，重复将$x$替换为$(x+1) \bmod 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. (第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未标记，将其标记。