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

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

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

共 $T$ 组数据。$1\le T\le 10^5$，$1\le k\le n\le10^9$，$1\le d\le 10^9$。

—— by Register_int