У нас \(N\) стільців, які розташовані по колу і один з них — трон. Степан спочатку сидить на стільці, який знаходиться на \(C\)  стільців від трону за годинниковою стрілкою.

Степан повторить хід нижче.

• підійде до стільця, який знаходиться на відстані \(K\) стільців від стільця, на якому він зараз сидить ( рахуємо за годинниковою стрілкою). Сідає на нього.

Через скільки ходів він вперше сяде на трон?

Якщо він ніколи не зможе сісти на трон, то виведіть -1.

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

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

Потім слідують \(T\) рядків, кожен рядок містить цілі числа \(N, S, K\) (\(2 \le N \le 10^9\), \(1 \le S < N\), \(1 \le K \le 10^9\)).

Числа у рядках розділяються пропуском.

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

У вихідний потік виведіть, для кожного тесту в окремому рядку, відповідь.

Примітка

До прикладу 1:

У першому тестовому випадку ми маємо 10 стільців і Степан спочатку сидить на стільці, який знаходиться на відстані 4 стільців від трону за годинниковою стрілкою. Він сяде на трон після 2 ходів переміщення на 3 стільці за годинниковою стрілкою. У другому тестовому випадку він ніколи не сяде на трон, тому ми виводимо -1.

Приклад вхідних даних

4
10 4 3
1000 11 2
998244353 897581057 595591169
10000 6 14

Приклад вихідних даних

2
-1  
249561088
3571