Bạn có hai bình đựng nước. Bình thứ nhất chứa 𝑎 lít nước, bình thứ 2 chứa 𝑏 lít nước. Cả
hai bình đều rất lớn và có thể chứa bất kỳ lượng nước nào.
Bạn cũng có một chiếc cốc rỗng có thể chứa được 𝑐 lít nước.
Trong một thao tác, bạn có thể sử dụng cốc 𝑐 lít nước để múc từ một bình và đổ vào bình
kia. Lưu ý rằng bạn có thể không cần múc đầy cốc nước thể tích c lít để đổ vào bình.
Cần phải thực hiện ít nhất bao nhiêu lần để thể tích nước trong hai bình bằng nhau? Lưu
ý rằng bạn không thể thực hiện bất kỳ thao tác nào khác ngoài các thao tác được mô tả ở trên.
Dữ liệu vào:
Dòng đầu tiên chứa số 𝑡 (1 ≤ 𝑡 ≤ 100) là số lượng test.
𝑡 dòng tiếp theo, mỗi dòng chứa ba số nguyên 𝑎, 𝑏 và 𝑐 (1 < 𝑎, 𝑏, 𝑐 < 100) - tương ứng là khối
lượng nước trong bình và dung tích của cốc.
Kết quả ra:
Gồm 𝑡 dòng, mỗi dòng chứa số nguyên dương là số lần thao tác đổ nước ít nhất để 2 bình bằng
nhau.
Ví dụ:
INPUT

6
3 7 2
17 4 3
17 17 1
17 21 100
1 100 1
97 4 3 

OUTPUT

1

3

0

1
50
16