问题描述

有 $n$ 个排成一个环的格子，编号为 $0\sim n-1$。现在进行如下操作：

• 选择 $0$ 号格子，将其打上标记。
• 选择 $d$ 个格子后的第一个尚未被标记的格子，将其打上标记。
• 重复执行直到所有格子都被打上标记。

你需要输出第 $k$ 次标记的格子的编号。

输入格式

第一行输入一个整数 $T$。表示共 $T$ 组数据。

接下来 $T$ 行，每行 $3$ 个整数 $n,d,k$；

输出格式

输出 $T$ 行，每行一个答案。

样例

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

数据范围

$1\le T\le 10^5$，$1\le k\le n\le10^9$，$1\le d\le 10^9$。