Оксані подобаються всі числа, які діляться на \(А\). Степану не подобаються числа, які діляться на \(B\), і подобаються всі числа, що залишилися.

Визначте найменше число, більше або дорівнює \(N\), яке подобається і Оксані, і Степану.

Виведіть -1, якщо такого числа не існує.

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

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

Перший і єдиний рядок кожного тесту містить три цілі числа \(A\), \(B\) і \(N\)

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

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

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

Примітка

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

15 — це найменше число ≥ 11, яке ділиться на 5 і не ділиться на 2.

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

3
5 2 11
4 3 24
7 7 100

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

15
28
-1