You've got two numbers. As long as they are both larger than zero, they go through the same operation: subtract the lesser number from the larger one. If they equal substract one number from the another. For example, one operation transforms pair (4,17) to pair (4,13), it transforms (5,5) to (0,5).

You've got some number of pairs (a_{i}, b_{i}). How many operations will be performed for each of them?


-----Input-----

The first line contains the number of pairs n (1  ≤  n  ≤  1000). Then follow n lines, each line contains a pair of positive integers a_{i}, b_{i} (1  ≤  a_{i},  b_{i}  ≤  10^9).


-----Output-----

Print the sought number of operations for each pair on a single line.


-----Examples-----
Input
2
4 17
7 987654321

Output
8
141093479

Difficulty: interview

Starter code:

Solutions:
T=int(input())
answer=[]
for t in range(T):
    A,B=input().split()
    A=int(A)
    B=int(B)
    x=0
    if(A>B):
        r=B
        B=A
        A=r
    while(A>0 and B>0):
        r=B//A
        x+=r
        r*=A
        B=B-r
        if(A>B):
            r=B
            B=A
            A=r
    answer.append(x)

for t in range(T):
    print(answer[t])

        


import sys

def get(a, b):
    if (a == 0 or b == 0):
        return 0
    if (a == b):
        return 1
    if (a > b):
        return get(b, a)

    res = b // a
    b = b % a
    return get(b, a) + res

ntest = int(input())
for i in range(0, ntest):
    tmp = list(map(int, input().split()))
    a = tmp[0]
    b = tmp[1]
    print(get(a, b))


n=int(input())

for i in range(n):
    ans=0
    x,y=list(map(int,input().split()))
    if(y>x):
        x,y=y,x

    while(y>0):
        ans+=x//y
        x=x%y
        x,y=y,x
    print(ans)


n=int(input())
y=[]
for x in range(n):
        y.append(input())

for x in y:
        noop=0
        lst1=x.split()
        lst1=[int(p) for p in lst1]
        ma=max(lst1)
        mi=min(lst1)
             
        while(ma!=0 and mi!=0):
                b=ma//mi
                ma=ma-b*mi
                temp=ma
                ma=mi
                mi=temp
                noop+=b
        print(noop)
                


for i in range(int(input())):
    a, b = map(int, input().split())
    if a > b: a, b = b, a
    s = 0
    if a > 0:
        s = b // a
        a, b = b - s * a, a
        while a > 0:
            k = b // a
            a, b = b - k * a, a
            s += k
    print(s)

n = int(input())
for i in range(n):
    t = input()
    t = list(t.split())
    a = int(t[0])
    b = int(t[1])
    if (a > b):
        (a , b) = (b , a)
    count = 0
    while (a != 0 and b != 0):
        count += b // a
        b %= a
        if (a > b):
            (a , b) = (b , a)
    print (count)


a=int(input())
while a>0:
 b=[int(i)for i in input().split()]
 c=0
 while b[0]*b[1]!=0:
  c+=b[1]//b[0]
  b[0],b[1]=b[1]%b[0],b[0]
 print(c)
 a-=1

import sys
import math

n = int(sys.stdin.readline())

for i in range(n):
	a, b = [int(x) for x in (sys.stdin.readline()).split()]
	v = 0
	while(a >= 1 and b >= 1):
		if(a < b):
			v += int(b / a)
			b %= a
		else:
			v += int(a / b)
			a %= b
	print(v)


def operate(a, b):
	if a > b:
		if (a - b) % b: return (a - b)//b
		else: return (a-b)//b + 1
	if b > a:
		if (b-a) % a: return (b-a)//a
		else: return (b-a)//a + 1

for x in range(int(input())):
	a, b = [int(x) for x in input().split()]
	count = 0
	while a != 0 and b != 0:
		if a > b:
			factor = (a-b)//b + 1
			a -= factor*b
			count+=factor
		else:
			factor = (b-a)//a+1
			b -= factor*a
			count+=factor
	print(count)

#!/usr/bin/env python
# -*- coding: utf-8 -*-

n = int(input())
for i in range(n):
    a, b = list(map(int, input().split()))

    ans = 0
    while b:
        ans += (a // b)
        a, b = b, a % b

    print(ans)


__author__ = 'markdaniel'

def main():
    num1, num2 = [int(x) for x in input().split(' ')]
    maxval = max(num1, num2)
    minval = min(num1, num2)
    ops = 0
    while maxval > 0 and minval > 0:
        remainderMultiple = ((maxval - minval) // minval)
        maxval -= remainderMultiple * minval
        ops += remainderMultiple
        maxval -= minval
        ops += 1
        if maxval < minval:
            temp = maxval
            maxval = minval
            minval = temp

    return ops

def __starting_point():
    cases = int(input())
    for i in range(cases):
        print(main())
__starting_point()

def larger(a,b,count):
    if b == 0:
        return count

    if a > b:
        a,b = b,a

    count += (b//a)
    count = larger(a,b%a,count)
    return count

testCase = input()
for _ in range(int(testCase)):
    a = list(map(int,input().split(' ')))
    print(larger(a[0],a[1],0))


n=int(input())
for i in range(n):
	a,b = map( int, input().split() )
	if a>b: a,b=b,a
	ans=0
	while a>0:
		ans+=b//a
		b%=a
		a,b=b,a
	print(ans)

import sys

line = input().split(" ");

test_cases = int(line[0]);

for tc in range(test_cases):
    line = input().split(" ");
    num1 = int(line[0]);
    num2 = int(line[1]);
    count = 0;
    while(num1 != 0 and num2 != 0):
        if(num1 > num2):
            count += int(num1/num2);
            num1 %= num2;
        else:
            count += int(num2/num1);
            num2 %= num1;
    
    sys.stdout.write(str(count));
    if(tc < test_cases-1):
        sys.stdout.write("\n");

from sys import stdin

N = int(stdin.readline())

for n in range(N):
	a, b = map(int, stdin.readline().split())

	a, b = min(a, b), max(a, b)

	ops = 0
	while a > 0:
		ops += b // a
		a, b = b % a, a

	print(ops)

f=lambda x,y:f(y%x,x)+y//x if x else 0
I=input
for _ in'0'*int(I()):a,b=map(int,I().split());print(f(a,b))

for i in range(int(input())):
    a, b = map(int, input().split())
    operations = 0
    a, b = max(a,b), min(a,b)
    while b != 0:
        operations += a//b
        a -= a//b*b
        a, b = max(a,b), min(a,b)
    print(operations)

import math, sys

def solve(a, b):
    if a == b:
        return 1
    elif a == 0 or b == 0:
        return 0
    else:
        return math.floor(max(a,b)/min(a,b)) + solve(min(a,b), max(a,b) % min(a,b))

def main():
    n = int(input())
    for s in sys.stdin:
        a, b = [int(x) for x in s.split()]
        print(solve(a,b))

def __starting_point():
    main()

__starting_point()

def solve():
    a, b = list(map(int, input().rstrip().split()))
    count = 0
    if b > a:
        a, b = b, a
    while not (a == 0 or b == 0):
        count += a // b
        a %= b
        a, b = b, a
    print(count)

def __starting_point():
    t = int(input())
    for _ in range(t):
        solve()

__starting_point()

#!/usr/bin/env python3

# ------------------------------
# cs104c/assignment7/CutRibbon.py
# Copyright (C) 2017
# Drew Romanyk
# ------------------------------

# -------
# imports
# -------

import math
import sys


# -------
# solve
# -------

def solve(r, w):
    """
    :param r:
    :param w:
    :return:
    """
    num_pairs = int(r.readline())
    pairs = []
    for _ in range(num_pairs):
        line_data = [int(v) for v in r.readline().split()]
        pairs.append((line_data[0], line_data[1],))

        num_1 = line_data[0]
        num_2 = line_data[1]
        ops = 0

        while num_1 > 0 and num_2 > 0:
            if num_1 > num_2:
                num_1, num_2 = num_2, num_1
            ops += num_2 // num_1
            num_2 %= num_1

        print(ops)


# -------
# main
# -------

def __starting_point():
    solve(sys.stdin, sys.stdout)

__starting_point()

T = int(input())
for t in range(T):
    x, y = [int(n) for n in input().split()]
    ops = 0
    while x and y:
        if x < y:
            ops += int(y/x)
            y = y % x
        elif y < x:
            ops += int(x/y)
            x = x % y
        else:
            ops += 1
            break
    print(ops)