Погане число#377
Джон і Брус вважають, що число — дуже погане число. Тому вони намагаються уникати його завжди і всюди.
Тепер хлопці хочуть подати число у вигляді суми додатних чисел, кожне з яких не перевищує . Проте не забувайте про погане число ! Кожен доданок не повинен ділитися на , і кількість доданків також не повинна ділитися на .
Ваша задача — знайти мінімально можливу кількість доданків у такому представленні числа .
Наприклад, якщо N=3, M=11, K=6, то ми можемо подати як 5+6, але ділиться на , отже треба як мінімум доданки. Але оскільки N=3, ми не можемо мати доданки, тому відповідь — . Один із можливих способів подати : 11=4+4+2+1.
Перший рядок містить одне ціле число — кількість тестів. Кожен тест складається з одного рядка, в якому записано три цілі числа , і , розділені пробілами.
Для кожного тесту виведіть в окремому рядку мінімально можливу кількість доданків відповідно до зазначених вимог. Якщо це неможливо, виведіть -1 (без лапок).
Обмеження
1 \le T \le 74 1 \le N, M, K \le 1000000000~(10^9)
Приклад 1