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 1 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

• 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\).

Example

2
15 24 3
100 27 8

5
5