Bạn được cho 2 số nguyên \(a, b\).
Hãy làm việc này sau đây cho đến khi một trong hai số \(a, b\) là số 0 :
- Nếu \(b \leq a\) thì lấy a trừ đi b \((a = a - b)\).
- ngươc lại lấy b trừ a\((b = b - a)\).
Nhập vào 2 số \(a, b\). Hãy đếm số lần bạn làm công việc trên
Input
-
\(t (t \leq 1000)\) - số test
-
\(t\) dòng, mỗi dòng gồm 2 số nguyên dương \(a, b (a, b \leq 1000000000)\)
Output
- \(t\) dòng, số lần thực hiện để một trong 2 số \(a, b\) có 1 số là số 0
Example
Test 1
Input
1
4 17Output
8Note
\((4\ 17) \rightarrow (4\ 13) \rightarrow (4\ 9) \rightarrow (4\ 5) \rightarrow (4\ 1) \rightarrow (3\ 1) \rightarrow (2\ 1) \rightarrow (1\ 1) \rightarrow (0\ 1)\)
Bình luận
Đăng nhập để bình luận
Chưa có bình luận nào.