Time Limit: 1.0 s

Memory Limit: 256.0 MB

Description

You ar given two positive integer \(A\) and \(B\). in one operation you can do the following :-

• Update the value of MAX(A,B) := |\(A\)-\(B\)|

for example, suppose A=20,B=12

After first operation A=8, B=12 (maximum of (A,B) is A, so update A = |A-B| = |20-12| = 8
After second operation A=8, B=4
After third operation A=4, B=4
After fourth operation A=0, B=4

Count the minimum number of operations after that either \(A\) or \(B\) becomes zero.

note: |X| denotes the absolute value of X.for example |5|=5, |-5|=5

Input

First line of input contains an integer \(T\) : number of testcases
Each of next \(T\) lines takes input two integers \(A,B\)
1 <= \(T\) <= 1000
1 <= \(A,B\) <= 10^18

Output

Output \(T\) lines, each line should contain an integer : minimum number of operations after that either \(A\) or \(B\) becomes zero.

Sample

2
20 12
2 5

4
4

testcase 1 has been discussed into problem statement.

all the steps are as follows :
a=2,b=3
a=2,b=1
a=1,b=1
a=0,b=1