Є \(N\) квадратів з індексами від 0 до \((N−1)\), розташованих у лінію. Степан збирається позначити кожен квадрат за наступною процедурою.

• Позначте квадрат 0.

• Повторіть наступні кроки 1 - 3 \((N−1)\) разів.

  1. Ініціалізуйте змінну \(x\) за допомогою \((A + D)\) mod \(N\), де \(A\) є індексом квадрата, позначеного минулого разу.

  2. Поки квадрат \(x\) позначено, повторіть заміну \(x\) на \((x + 1)\) mod \(N\).

  3. Познач квадрат \(х\).

Знайдіть індекс квадрата, який Степан позначає \(K\)-й раз.

Дано \(T\) тестових випадків, знайдіть відповідь для кожного з них.

Обмеження

• \(1≤T≤10^5\)
• \(1≤K≤N≤10^9\)
• \(1≤D≤10^9\)
• Усі значення у вхідних даних є цілими числами.

Формат вхідних даних

Перший рядок містить ціле число \(T\) - кількість тестів.

Потім слідують \(T\) рядків, кожен рядок містить цілі числа \(N, D, K\).

Формат вихідних даних

У вихідний потік виведіть \(Т\) рядків.

\(I\)-й \((1≤i≤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, Степан позначає квадрати наступним чином.

• Позначте квадрат 0.
• (1-ша ітерація) Нехай \(x\)=(0 + 2) mod 4=2. Оскільки квадрат 2 не позначено, позначте його.
• ( 2-а ітерація) Нехай \(x\)=(2 + 2) mod 4=0. Оскільки квадрат 0 позначено, нехай \(x\)=(0 + 1) mod 4=1. Оскільки квадрат 1 не позначено, позначте його.
• (3-я ітерація) Нехай \(x\)=(1 + 2) mod 4=3. Оскільки квадрат 3 не позначений, позначте його.