shortest-way

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

Source: hackerearth | Difficulty: EASY
Tags: Mathematics


Solutions:
#!/usr/bin/python
def minMax(a, b):
	if(a-b>0):
		max=a
		min=b
	else:
		max=b
		min=a
	return max,min

T=int(eval(input()))
for t in range(0,T):
	a,b=input().split()
	a=int(a)
	b=int(b)
	count=0
	while (True):
		max,min=minMax(a,b)
		if(max==1 and min==1):
			count=count+0
			break
		if(max==1):
			count=count+min-1
			break
		if(min==1):
			count=count+max-1
			break
		count=count + max/min
		r=max%min
		if (r==1):
			count=count+min-1
			break
		else:
			 a=r
			 b=min
	print(count)


t=int(input())
for _ in range(t):
	a,b=list(map(int,input().split()))
	ans=0
	while True:
		if a==1 and b==1:
			break
		if a>b:
			ans+=int((a-1)/b)
			a=a-(int((a-1)/b)*b)
		else:
			ans+=int((b-1)/a)
			b=b-(int((b-1)/a)*a)
	print(ans)


test_cases=int(input())
for ite in range(test_cases):
	given_pair=[int(i) for i in 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)



__author__ = 'siddharth'

if __name__ == "__main__":

	T = int(input())

	for t in range(T):

		u, v = list(map(int, input().split()))

		CT = 0

		while u > 1 or v > 1:
			CT += u/v
			CT -= 0 if v != 1 else 1
			t = u%v
			u = v
			v = t

		print(CT)



def gcd(a,b):
	if b==0:
		return a
	return gcd(b,a%b)
t=eval(input())
while t>0:
	t=t-1
	a,b=list(map(int,input().split()))
	r=0
	while a>0 and b>0:
		if a>b:
			r=r+a/b
			a=a%b
		else:
			r=r+b/a
			b=b%a
	print(r-1)


t=int(input())
for i in range(t):
	inj=input().split()
	a=int(inj[0])
	b=int(inj[1])
	ans=0
	while((a>1) and (b>1)):
		if a>b:
			ans=ans+a/b
			a=a%b
		elif b>a:
			ans=ans+b/a
			b=b%a
	print(ans+max(a-1,b-1))


tc=int(eval(input()))
while tc>0:
	a,b=list(map(int,input().split()))
	rs=0
	while a>0 and b>0:
		if a>b:
			rs=rs+int(a/b)
			a=a%b
		else:
			rs=rs+int(b/a)
			b=b%a
	print(rs-1)
	tc=tc-1


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
T = int(input())
for _ in range(T):
	a, b = list(map(int, input().split()))
	count = 0
	if a < b:
		a, b = b, a
	while b != 0:
		count += a / b
		a, b = b, a % b
	print(count - 1)



for _ in range(eval(input())):
	a, b = list(map(int, input().split()))
	res = 0
	while a > 0 and b > 0:
		if a > b:
			res += a / b
			a %= b
		else:
			res += b / a
			b %= a
	print(res - 1)        


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
#print 'Hello World!'
t=int(input())
for i in range(t):
	a,b=list(map(int,input().split()))
	r=0
	while([a,b]!=[1,1] and [a,b]!=[0,1] and [a,b]!=[1,0]):
		if(a>b):
			r=r+a//b
			a=(a%b)
		else:
			r=r+b/a
			b=(b%a)
	if(a==1 and b==1):
		print(0)
	else:
		
		print(r-1)