Точное количество капель
- Хм... Я же просил 400 капель, а здесь 402.
- Здесь 400 капель, у нас все точно.
Русский мультфильм "Тайна третьей планеты"
Думаете управлять рестораном легко? Это не тот случай, если все клиенты требовательны.
Вы управляете рестораном, и каждый день множество людей приходит и заказывает у Вас напитки. Поскольку Ваш ресторан открылся совсем недавно, то у Вас еще нет никаких сосудов, за исключением двух, которые могут вместить в себя в точности a и b капель жидкости соответственно. Чтобы не заставлять Ваших клиентов ждать (или по крайней мере свести к минимуму их время ожидания), Вам следует определить минимальное количество действий, необходимых для получения в точности c капель жидкости в одном из сосудов.
Сначала оба сосуда пусты. Действиями считаются следующие операции:
опорожнение сосуда;
заполнение сосуда;
переливание жидкости из одного сосуда в другой (без ее пролития) пока один из сосудов не наполнится или не станет пустым.
В конце концов Вы устали делать это вручную, и решили написать программу, которая поможет рассчитать наименьшее количество операций, необходимых для получения требуемого.
Входные данные
Первая строка содержит количество тестов t (1 ≤ t ≤ 10^5). Каждая из следующих t строк содержит три целых числа a, b и c (1 ≤ a, b, c ≤ 10^9).
Выходные данные
Для каждого теста выведите наименьшее количество действий, достаточных для получения в точности c капель жидкости в одном из сосудов, либо -1 если этого сделать невозможно.