\textit{- Hmm... I asked for 400 drops, but there are 402 here.} \textit{- 400 drops, we never make mistakes.} Russian cartoon _The Mystery of the Third Planet Do you think that managing a restaurant is easy? That is not the case when all clients are pretty demanding. You are managing a restaurant, and every day a lot of people come and ask you to give them some drinks. As your restaurant has just recently opened, you don't have any vessels except two, which can accommodate \textbf{a} drops of liquid and \textbf{b} drops of liquid, respectively. In order not to make your clients wait (or at least to minimize their waiting time), you always have to determine the minimal number of steps required to obtain exactly \textbf{c} drops of liquid in one of the vessels. At the beginning both vessels are empty. The following operations are counted as steps: \begin{itemize} \item emptying a vessel; \item filling a vessel; \item pouring liquid from one vessel to the other (without spilling) until one of the vessels is either full or empty. \end{itemize} Eventually you became tired to do it all by hand and decided to write a program which will help you calculate the minimum number of steps required in all these cases. \InputFile The first line contains the number of test cases \textbf{T} (\textbf{1} ≤ \textbf{T} ≤ \textbf{10^5}). Each of the next \textbf{T} lines contains one testcase and consists of three integers \textbf{a}, \textbf{b} and \textbf{c} (\textbf{1} ≤ \textbf{a}, \textbf{b}, \textbf{c} ≤ \textbf{10^9}). \OutputFile For each test case print the minimum number of steps required to obtain exactly \textbf{c} drops of liquid in one of the vessels or \textbf{-1} if this is impossible.