F. Переливания
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вова нашел две пустые бутылки. Одна могла вместить в себя n литров воды, а другая — m литров. Вова может выполнять следующие действия:

  1. Полностью наполнить одну из бутылок водой;
  2. Вылить из одной из бутылок всю воду;
  3. Перелить воду из одной бутылки в другую, пока одна из них не наполнится или другая опустошится.

Вова интересуется, а за какое минимальное количество таких действий он сможет получить ровно k литров воды в одной из бутылок?

Входные данные

В первой строке задано одно целое число t — количество тестовых примеров.

В следующих t строках задано по три целых числа n, m и k — емкости бутылок и количество воды, которое нужно получить, соответственно.

1 ≤ t ≤ 100
1 ≤ n, m, k ≤ 109
Выходные данные

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

Пример
Входные данные
2
30 37 10
6 8 13
Выходные данные
42
-1