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