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

1
4 17

8