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.

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


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 compute_gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def compute_lcm(x, y):
	lcm = x * y // compute_gcd(x, y)
	return lcm
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))


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.141592653589793
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)


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

def isprime(x):
	i = 2
	while i * i <= x:
		if x % i == 0:
			return 0
		i += 1
	return 1

def isSumOfKprimes(N, K):
	if N < 2 * K:
		return 0
	if K == 1:
		return isprime(N)
	if K == 2:
		if N % 2 == 0:
			return 1
		return isprime(N - 2)
	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

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)

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)


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))


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))


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)


import math
for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	t = math.gcd(n, m)
	t2 = n * m // t
	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)


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)


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)

	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(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)
			res = l / a + l / b
			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)


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)