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^18

a and b are co-primes

SAMPLE INPUT
2 
1 1
5 2

SAMPLE OUTPUT
0 
3
test_cases=int(raw_input())
for ite in range(test_cases):
	given_pair=[int(i) for i in raw_input().split()]
	num_operations=0
	while given_pair!=[1,1] and given_pair!=[1,0] and given_pair!=[0,1]:
		if given_pair[0]>given_pair[1]:
			num_operations+=given_pair[0]//given_pair[1]
			given_pair[0]%=given_pair[1]
		else:
			num_operations+=given_pair[1]//given_pair[0]
			given_pair[1]%=given_pair[0]
	if given_pair==[1,1]:
		print 0
	else:
		print num_operations-1