Cho một thùng nước và hai gáo nước có dung tích lần lượt là ~A~ và ~B~. Ban đầu thùng nước rỗng. Một người phải dùng hai gáo nước múc nước vào thùng với điều kiện khi múc vào hay múc ra đều phải đong đầy gáo. Hãy tìm cách dùng số lần múc nước ít nhất để có được lượng nước là ~C~ trong thùng.

Input:

• Dòng đầu chứa số ~k \le 100~ là số test;
• ~k~ dòng tiếp theo, mỗi dòng chứa ba số nguyên dương ~A, B, C \le 10^9~ cách nhau bởi dấu cách tương ứng với một test.

Output:

• Ứng với mỗi test, ghi ra trên một dòng một số nguyên duy nhất là số lần múc theo phương án tìm được, nếu không thể thực hiện yêu cầu ghi ra số ~-1~.

Sample Input 1

2
15 24 3
100 27 8

Sample Output 1

5
5

Tính điểm:

• Test case ~1~: Dùng gáo ~24~ múc vào ~2~ lần và dùng gáo ~15~ đổ ra ~3~ lần;
• Test case ~2~: Dùng gáo ~27~ múc vào ~4~ lần và dùng gáo ~100~ múc ra ~1~ lần.