Cho hai số nguyên dương \(a\), \(b\). Lặp lại thao tác sau cho đến khi một trong hai số bằng 0:

• Nếu \(b \le a\), đặt \(a = a - b\)
• Ngược lại, đặt \(b = b - a\)

Hãy đếm số bước thực hiện cho đến khi một trong hai số \(a\) hoặc \(b\) bằng 0.

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên \(t\) (\(t \le 1000\)) — số lượng bộ test
• \(t\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(a\), \(b\) (\(a, b \le 10^9\))

Dữ liệu ra: \(t\) dòng, mỗi dòng là số bước thực hiện cho đến khi một số bằng 0.

Ví dụ:

Giải thích: \((4, 17) \to (4, 13) \to (4, 9) \to (4, 5) \to (4, 1) \to (3, 1) \to (2, 1) \to (1, 1) \to (0, 1)\), tổng cộng 8 bước.

Giới hạn

• \(t \le 1000\)
• \(1 \le a, b \le 10^9\)
• Kết quả mỗi bộ test không vượt quá \(10^{18}\)
• Thời gian: 1 giây
• Bộ nhớ: 256 MB