Hùng có hai bình nước rỗng m lít và n lít. Hùng đến bên bờ sông và tìm cách đong đúng d lít nước ở một trong hai bình. Có 3 loại thao tác:

• Đổ đầy một bình;
• Đổ hết một bình;
• Đổ từ bình này sang bình kia cho đến khi hoặc bình nhận đầy hoặc bình đổ rỗng.

Yêu cầu: Tìm cách đong đúng d lít với số thao tác sử dụng ít nhất.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên dương T ≤ 1000 là số lượng test.
Mỗi dòng trong số T dòng tiếp theo tương ứng với một test chứa 3 số nguyên dương m, n, d ≤ 10⁸ .

Kết quả

Mỗi test ghi trên một dòng một số nguyên là số lượng ít nhất thao tác để thu được đúng d lít nước. Ghi ra -1 nếu không có cách nào thu được d lít nước.