See Russian Translation

The statement of this problem is quite short , apt and clear. We don't want any coder to spend time in reading a lengthy, boring story that has no connection with the actual problem.

The problem states:

Given a pair (1,1), your aim is to get a new pair (a,b) in minimum number of operations.

There are two types of operations you can use:

1.) If the pair is ( x , y ) then change it to ( x+y, y )

2.) If the pair is ( x , y ) then change it to ( x, x+y )

It is guaranteed that a and b are co-prime .

Input:

The first line contains the number of test cases T. Then, T lines follow, where each line contains a and b respectively.

Output:

Print a line containing the minimum number of operations required to achieve the given fraction, corresponding to each test case.

Constraints:

1 <= T <=10

1<= a,b <=10¹⁸

a and b are co-primes