Задачі
Точна кількість крапель
Точна кількість крапель
\textit{- Хм... Я ж просив 400 крапель, а туть 402.}
\textit{- Тут 400 крапель, у нас усе точно.}
Російський мультфільм "Таємниця третьої планети"
Думаєте керувати рестораном легко? Це не той випадок, якщо усі клієнти вимогливі.
Ви керуючий рестораном, і щодня велика кількість людей приходить і замовляє у Вас напої. Оскільки Ваш ресторан відкрився зовсім нещодавно, то у Вас ще немає ніяких чаш, за винятком двох, які можуть помістити у себе в точності \textbf{a} та \textbf{b} крапель рідини відповідно. Щоб не заставляти Ваших клієнтів чекати (або по меншій мірі звести до мінімуму їх час очікування), Вам потрібно визначити мінімальну кількість дій, необхідни для отримання у точності \textbf{c} крапель рідини у одній з чаш.
Спочатку обидві чаші порожні. Діями вважаються наступні операції:
\begin{itemize}
\item спорожнення чаші;
\item заповнення чаші;
\item переливання рідини з однієї чаші в іншу (без її пролиття) доки одна з чаш не наповниться чи не стане порожньою.
\end{itemize}
В кінці кінців Ви втомились робити це вручну, і вирішили написати програму, яка допоможе розрахувати найменшу кількість операцій, необхідних для отримання того, що вимагається.
\InputFile
Перший рядок містить кількість тестів \textbf{t }(\textbf{1 }≤ \textbf{t }≤ \textbf{10^5}). Кожен з наступних \textbf{t }рядків містить три цілих числа \textbf{a}, \textbf{b} та \textbf{c }(\textbf{1 }≤ \textbf{a}, \textbf{b, c }≤ \textbf{10^9}).
\OutputFile
Для кожного тесту виведіть найменшу кількість дій, достатніх для отримання у точності \textbf{c }крапель рідини в одній з чаш, або \textbf{-1 }якщо це зробити неможливо.
Вхідні дані #1
2 2 5 4 5 3 7
Вихідні дані #1
4 -1