Джон и Брюс считают, что число N является очень плохим числом. Поэтому они пытаются избежать его в любое время и повсеместно.
Теперь ребята хотят представлять число М в виде суммы положительных чисел, каждое из которых не превышает К. Но не стоит забывать о плохом числе N! Каждое слагаемое не должно быть кратно N, причем количество слагаемых также не должна делиться на N.
Ваша задача найти минимально возможное количество слагаемых в таком представлении М.
Например, если N = 3, M = 11, К = 6, то мы можем представить как M=5+6, но число 6 делится на 3, значит, у нас должно быть, по крайней мере, 3 слагаемых. Но поскольку N = 3, то мы не можем иметь 3 слагаемых и, следовательно, ответ будет 4. Один из возможных способов представления М:
11 = 4 + 4 + 2 + 1.
Первая строка содержит одно целое число Т - количество тестов. Каждый тест состоит из одной строки, содержащей три целых числа N, M и K, разделенных одним пробелом.
Для каждого теста вывести одну строку, содержащую минимальное возможное количество слагаемых в соответствии с требованиями, описанными выше. Если это невозможно, выведите "-1" (без кавычек).
Ограничения
1 <= T <= 74,
1 <= N, M, K <= 1000000000 (10^9).