Hai bình nước

Có hai bình rỗng, bình thứ nhất chứa được tối đa $A$ lít, bình thứ hai chứa được tối đa $B$ lít, và một vòi nước không giới hạn. Mỗi thao tác là một trong các việc sau:

• đổ đầy một bình từ vòi;
• đổ hết nước trong một bình đi;
• rót nước từ bình này sang bình kia cho đến khi bình rót cạn hoặc bình nhận đầy.

Bình không có vạch chia, nên chỉ thực hiện được đúng các thao tác trên. Hãy tìm số thao tác ít nhất để một trong hai bình chứa đúng $t$ lít, hoặc in $-1$ nếu không làm được.

Mỗi tệp dữ liệu gồm nhiều bộ test độc lập.

Dữ liệu vào

• Dòng đầu chứa số bộ test $T$.
• Mỗi bộ test gồm một dòng chứa ba số nguyên $A,B,t$.

Dữ liệu ra

Với mỗi bộ test, in một số nguyên trên một dòng: số thao tác ít nhất, hoặc $-1$.

Ràng buộc

• $1\le T\le {10}^4$
• $1\le A,B$ và $1\le t\le max(A,B)$
• Tổng $A+B$ trên mọi bộ test không vượt quá ${10}^5$

Ví dụ