Cho một thùng nước và hai gáo nước có dung tích lần lượt là và . 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à trong thùng.
Dữ liệu vào:
Dòng đầu chứa số là số test;
dòng tiếp theo, mỗi dòng chứa ba số nguyên dương cách nhau bởi dấu cách tương ứng với một test.
Dữ liệu ra:
Ứ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ố .
Ví dụ:
Dữ liệu vào:
2
15 24 3
100 27 8
Dữ liệu ra:
5
5
Giải thích:
Test case Dùng giáo múc vào lần và dùng gáo đổ ra lần;
Test case Dùng gáo múc vào lần và dùng gáo múc ra lần.
