Chef made two laddus with sweetness X and Y respectively. Cheffina comes and sees the chef created two laddus with different sweetness (might be same). Cheffina has the magical power to make the sweetness of laddus equal. Cheffina requires 1 unit of power to increase the sweetness of laddu by its original value i.e. 1 unit to convert Z to 2Z and 2 unit to convert Z to 3Z and so on… How many units of power does cheffina want to make the sweetness equal?

-----Input:-----
- First-line will contain $T$, the number of test cases. Then the test cases follow. 
- Each test case contains a single line of input, two integers $X, Y$. 

-----Output:-----
For each test case, output in a single line answer as power required.

-----Constraints-----
- $1 \leq T \leq 10^5$
- $1 \leq X,Y \leq 10^5$

-----Sample Input:-----
2
2 2
4 6

-----Sample Output:-----
0
3

-----EXPLANATION:-----
For 1) Sweetness are same so no need to use power.
For 2) 
1st laddu
2 Unit power = 4 -> 12
2nd Laddu
1 Unit power = 6 -> 12
After using total 3 unit power sweetness of both laddus are same.

Difficulty: interview

Starter code:

Solutions:
def gcd(a,b):
	if b==0:return a
	else:return gcd(b,a%b)
def lcm(a,b):
	m=a*b
	g=gcd(a,b)
	return int(m/g)
for _ in range(int(input())):
	x,y=[int(x) for x in input().split()]
	l=lcm(x,y)
	s=int(l/x)
	t=int(l/y)
	print(s+t-2)

for i in range(int(input())):
    def gcd(a,b):
        if a == 0:
            return b
        return gcd(b % a, a)
    
    def lcm(a,b):
        return (a / gcd(a,b))* b
    x,y=map(int,input().split())
    lc=lcm(x,y)
    x=lc/x
    y=lc/y
    print(int(x+y-2))

# def find(x,y):
#     if x==y:
#         return 0
    
#     if x > y:
#       greater = x
#     else:
#       greater = y

#     while(True):
#       if((greater % x == 0) and (greater % y == 0)):
#           lcm = greater
#           break
#       greater += 1
#     return lcm
def compute_gcd(x, y):

   while(y):
       x, y = y, x % y
   return x

# This function computes LCM
def compute_lcm(x, y):
   
   lcm = (x*y)//compute_gcd(x,y)
   return lcm
# cook your dish here
t = int(input())


for i in range(t):
    x_y = input().split()
    x = int(x_y[0])
    y = int(x_y[1])
    if x == y:
        print(0)
    else:
        sweetness = compute_lcm(x,y)
        x = (sweetness/x)-1
        y = (sweetness/y)-1
        print(int(x+y))

# cook your dish here
def gcd(x, y):
    while y:
        x, y = y, x % y
    return x

def lcm(x, y):
    return (x*y)//(gcd(x,y))


abc="abcdefghijklmnopqrstuvwxyz"

pi=3.141592653589793238

t = int(input())
for _ in range(t):
    x,y = map(int,input().split())
    comm = lcm(x,y)
    x_n = comm//x - 1
    y_n = comm//y - 1
    print(x_n + y_n)

# cook your dish here
import math
t = int(input())
for i in range(t):
    x, y = list(map(int, input().split()))
    if x != y:
        l = x * y // math.gcd(x, y)
        a = (l // x) - 1
        b = (l // y) - 1
        print(a + b)
    else:
        print(0)


def gcd(a, b):
    if a == 0:
        return b
    return gcd(b % a, a)
def lcm(a, b):
    return (a / gcd(a, b)) * b
t=int(input())
for items in range(t):
    n,y=list(map(int,input().split()))
    if n==y:
        print('0')
    else:
        ans=lcm(n,y)
        first=(ans-n)//n
        second=(ans-y)//y
        print(int(first+second))


from collections import Counter
import string
import math
import sys
# sys.setrecursionlimit(10**6) 
def isprime(x): 
      
    # check for numbers from 2 
    # to sqrt(x) if it is divisible 
    # return false 
    i = 2
    while(i * i <= x): 
        if (x % i == 0): 
            return 0
        i+=1
    return 1
def isSumOfKprimes(N, K): 
      
    # N < 2K directly return false 
    if (N < 2 * K): 
        return 0
  
    # If K = 1 return value depends 
    # on primality of N 
    if (K == 1): 
        return isprime(N) 
  
    if (K == 2): 
          
        # if N is even directly 
        # return true; 
        if (N % 2 == 0): 
            return 1
  
        # If N is odd, then one  
        # prime must be 2. All  
        # other primes are odd 
        # and cannot have a pair 
        # sum as even. 
        return isprime(N - 2)
      
  
    # If K >= 3 return true; 
    return 1
from math import pow, floor 
  
res = 0
def checkRecursive(num, x, k, n): 
    nonlocal res 
    if (x == 0): 
        res += 1
      
    r = floor(pow(num, (1 / n))); 
  
    for i in range(k + 1, r + 1, 1): 
        a = x - int(pow(i, n)) 
        if (a >= 0): 
            checkRecursive(num, x - int(pow(i, n)), i, n) 
    return res 
  
# Wrapper over checkRecursive() 
def check(x, n): 
    return checkRecursive(x, x, 0, n) 
from fractions import Fraction
def array_int():
    return [int(i) for i in sys.stdin.readline().split()]
def vary(arrber_of_variables):
    if arrber_of_variables==1:
        return int(sys.stdin.readline())
    if arrber_of_variables>=2:
        return list(map(int,sys.stdin.readline().split())) 
def makedict(var):
    return dict(Counter(var))
testcases=vary(1)
fact=[1 for i in range(11)]
for i in range(1,10):
    fact[i]=fact[i-1]*i
for _ in range(testcases):
    n,k=vary(2)
    if n==k:
        print(0)
        continue
    print(((n*k)//math.gcd(n,k))//n+((n*k)//math.gcd(n,k))//k-2)
    
   
    
        

    
    


def gcd(a,b):
    if a == 0:
        return b
    return gcd(b % a, a)
 
# Function to return LCM of two numbers
def lcm(a,b):
    return (a // gcd(a,b))* b
t=int(input())
for i in range(0,t):
    n,m=map(int,input().split())
    k=lcm(n,m)
    a=(k//n)-1
    b=(k//m)-1
    print(a+b)

# cook your dish here
def gcd(a,b):
    if a == 0:
        return b
    return gcd(b % a, a)
def lcm(a,b):
    return (a / gcd(a,b))* b
T=int(input())
for i in range(T):
    init=list(map(int, input().split()))
    X=init[0]
    Y=init[1]
    q=lcm(X,Y)
    t1=q/X
    t2=q/Y
    print(int(t1+t2-2))

# cook your dish here
def lcm(a,b):
    from math import gcd
    return a*b// gcd(a,b)
    
itr = int(input())
for _ in range(itr):
    val= list(map(int,input().split()))
    a=val[0]
    b=val[1]
    l=lcm(a,b)
    f= l/a -1
    s= l/b -1
    print(int(f+s))
    




# cook your dish here
import math
t = int(input())
for i in range(t):
    x,y = list(map(int,input().split()))
    if x == y:
        print(0)
    else:
        a = math.gcd(x,y)
        b = x*y//(a)
        c = b//x
        d = b//y
        print(c+d-2)


# cook your dish here
import math
for _ in range(int(input())):
    n,m=list(map(int,input().split()))

    t=math.gcd(n,m)
    #print("t ",t)
    t2=(n*m//t)
    #print("t2 ",t2)
    print(t2//n-1 +t2//m-1)
  
            


def hcf(a,b): 
    if(b==0): 
        return a 
    else: 
        return hcf(b,a%b)
for i in range(int(input())):
    c=list(map(int,input().split()))
    if c[0]==c[1]:
        print(0)
    else:
        lcm=(c[0]*c[1]//hcf(c[0],c[1]))
        x=(lcm//c[0]-1)
        y=(lcm//c[1]-1)
        print(x+y)

# cook your dish here
for _ in range(int(input())):
    x,y=list(map(int,input().split()))
    a,b=x,y
    while(y):
        x, y = y, x % y
    k=x
    
    if (a+b)//k !=0:
    	print((a+b)//k  -2)
    else:
    	print(0)


def gcd(a, b):
    if a == 0:
        return b
    return gcd(b % a, a)
def lcm(a, b):
    return (a / gcd(a, b)) * b
t=int(input())
for items in range(t):
    n,y=list(map(int,input().split()))
    if n==y:
        print('0')
    else:
        ans=lcm(n,y)
        first=(ans-n)//n
        second=(ans-y)//y
        print(int(first+second))


T=int(input())
for i in range(T):
    arr=list(map(int,input().strip().split()))
    X=arr[0]
    Y=arr[1]

    def gcd(a,b):
    	if a == 0:
    		return b
    	return gcd(b % a, a)
    
    # Function to return LCM of two numbers
    def lcm(a,b):
    	return (a / gcd(a,b))* b
    
    num=lcm(X,Y)
    ans_X=num/X
    ans_Y=num/Y
    ans=int(ans_X+ans_Y-2)
    print(ans)


def compute_gcd(x, y):
   while(y):
       x, y = y, x % y
   return x
   
def f_lcm(x, y):
   lcm = (x*y)//compute_gcd(x,y)
   return lcm
   
   
t = int(input().strip())
for i in range(t):
    res = 0
    x_y = [int(i) for i in input().split()]
    x = x_y[0]
    y = x_y[1]
    lcm = f_lcm(x, y)
    temp = lcm
    if(x == y):
        print(0)
    else:
        res += lcm//x - 1
        res += lcm//y - 1
        print(res)
            
            
            
    


import math
for _ in range(int(input())):
    x,y=[int(x) for x in input().split()]
    if x==y:
        print(0)
        continue
    else:
        p=math.gcd(x,y)
        xx=(x*y)//p
        # print(xx)
        print(int((xx//x)+(xx/y)-2))
        


import math



def lcm(a,b):
    return abs(a*b) // math.gcd(a, b)



def __starting_point():
    t=int(input())
    for _ in range(t):
        li = list(map(int,input().split())) 
        a=li[0]
        b=li[1]
    
        if a==b :
            print(0)
        else:
            l=lcm(a,b)
            #print(l)
            res= (l/a) + (l/b)
            #print(l/a, b%l)
            print(int(res-2) )
__starting_point()

def computeGCD(x, y): 
  
   while(y): 
       x, y = y, x % y 
  
   return x
for _ in range(int(input())):
    x,y=list(map(int,input().split()))
    p=x*y
    g=computeGCD(x,y)
    l=p//g
    print((l//x)+(l//y)-2)
        
            


import math



def lcm(a,b):
    return abs(a*b) // math.gcd(a, b)



def __starting_point():
    t=int(input())
    for _ in range(t):
        li = list(map(int,input().split())) 
        a=li[0]
        b=li[1]
    
        if a==b :
            print(0)
        else:
            l=lcm(a,b)
            #print(l)
            res= (l/a) + (l/b)
            #print(l/a, b%l)
            print(int(res-2) )
__starting_point()

# cook your dish here
def gcd(a,b):
    if a==0:
        return b
    return gcd(b%a,a)
def lcm(a,b):
    return (a/gcd(a,b))*b
t=int(input())
for _ in range(t):
    x,y=list(map(int,input().split()))
    if x==y:
        print(0)
    else:
        a=lcm(x,y)
        print(int((a/x-1)+(a/y-1)))


from math import gcd 
def lcm(x,y):
    return x*y//(gcd(x,y)) 
for i in range(int(input())):
    n,m=list(map(int,input().split())) 
    k=lcm(n,m) 
    print(k//n+k//m-2)