Турнир по байтландским шахматам

При жеребьёвке первого этапа турнира по байтландским шахматам обнаружилась следующая проблема: требовалось выбрать одного из N участников, который все туры будет играть на одной доске.

Всего в турнире участвует N шахматистов. У организаторов имеется игральная кость с K сторонами. Они собираются с помощью этой игральной кости провести жеребьёвку и выбрать одного из N участников таким образом, чтобы вероятность быть выбранным для каждого участника была одинакова.

По заданным N и K вычислите, за каком минимальное число бросков i организаторы заведомо проведут жеребьёвку, или же определите, что такое i выбрать нельзя.

Формат ввода
В первой строке входа задано целое число 1 < T < 100 — количество тестовых примеров.

Каждый тестовый пример состоит из двух целых чисел N и K (1 < N,K <10^9) —количества участников и количества граней игральной кости соответственно.

Формат вывода
Для каждого тестового примера в отдельной строке выведите минимальное количество бросков кости, за которое организаторы заведомо проведут жеребьёвку, или же -1 в случае, если количество бросков может оказаться сколь угодно велико.

Пример
Ввод
3
4 8
8 4
5 3
Вывод
1
2
-1

0