Description

cxk有一个长度为 N 的数组a，编号从 0 到 N−1，cxk将以如下方式从1开始按顺序填数。

1. a[0]=1
2. 重复以下步骤 N−1 次
   1. 令x=(A+D)modN，其中A是上次填数的索引。
   2. 如果a[x]已经被填过了，重复更新x=(x+1)modN直到**a[x]**没被填过
   3. 往**a[x]**中填入下一个数

找到填写了 K 的索引。 对于给定的 T 个测试用例，找到每个测试用例的答案。

Format

Input

从标准输入中读取

1. 一个整数 T，表示接下来有 T 个测试用例：
   1. 三个整数N，D，K。

Output

• 对于每个测试用例：
  1. 输出一个整数，为该测试用例的答案

Samples

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

Limitation

• 1≤T≤10^5
• 1≤K≤N≤10^9
• 1≤D≤10^9
• 0.5s, 512KiB for each test case.