number of steps

Xem PDF

Điểm: 100 Thời gian: 0.3s Bộ nhớ: 640M Input: bàn phím Output: màn hình

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 17
Output
8
Note

\((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

Không có bình luận nào.