WATERJUG - Đong nước
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 512 megabyte
Đăng bởi: admin

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 ≤ 108 .

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.

Ví dụ

Input

2
3 8 5
3 4 5

Output

2
-1


Nguồn: ĐPT 20172018

Back to Top