Chef has two integers A and B.  
Chef wants to find the minimum value of \texttt{lcm}(A, X) - \texttt{gcd}(B, X) where X is any positive integer.

Help him determine this value.

Note: \texttt{gcd}(P, Q) denotes the [greatest common divisor] of P and Q and \texttt{lcm}(P, Q) denotes the [least common multiple] of P and Q.

------ Input Format ------ 

- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first and only line of each test case contains two space-separated integers A and B — the integers mentioned in the statement.

------ Output Format ------ 

For each test case, output the minimum value of \texttt{lcm}(A, X) - \texttt{gcd}(B, X).

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$1 ≤A, B ≤10^{9}$

----- Sample Input 1 ------ 
3
12 15
5 50
9 11

----- Sample Output 1 ------ 
9
0
8

----- explanation 1 ------ 
Test case $1$: For $X = 6$: $\texttt{lcm}(12, 6) - \texttt{gcd}(15, 6) = 12 - 3 = 9$ which is the minimum value required.

Test case $2$: For $X = 50$: $\texttt{lcm}(5, 50) - \texttt{gcd}(50, 50) = 50 - 50 = 0$ which is the minimum value required.

Test case $3$: For $X = 1$: $\texttt{lcm}(9, 1) - \texttt{gcd}(11, 1) = 9 - 1 = 8$ which is the minimum value required.

Source: codechef | Difficulty: EASY
Tags: Number theory

Mathematics


Solutions:
import math
for i in range(int(input())):
	(a, b) = map(int, input().split())
	print(a - math.gcd(a, b))


import math
T = int(input())
for i in range(T):
	(A, B) = map(int, input().split())
	print(A - math.gcd(B, A))


def gcd(a, b):
	k = [a, b]
	ans = 0
	k.sort()
	if k[1] % k[0] == 0:
		return k[0]
	else:
		return gcd(k[0], k[1] % k[0])

def lcm(a, b):
	s = gcd(a, b)
	return a * b // s
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	m = gcd(a, b)
	print(abs(lcm(a, m) - gcd(b, m)))


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def lcm(a, b):
	return a / gcd(a, b) * b
T = int(input())
for i in range(T):
	(A, B) = map(int, input().split())
	print(int(lcm(A, gcd(A, B)) - gcd(A, gcd(A, B))))


import math
for t in range(int(input())):
	(x, y) = map(int, input().split())
	c = math.gcd(x, y)
	print(x - c)


t = int(input())
import math
for i in range(t):
	nums = input().split(' ')
	(a, b) = (int(nums[0]), int(nums[1]))
	print(a - math.gcd(a, b))


import math
for t in range(int(input())):
	(a, b) = map(int, input().split())
	ans = a - math.gcd(a, b)
	print(ans)


from collections import Counter
from math import gcd

def inparr():
	tmparr = [int(i) for i in input().split()]
	return tmparr
for _ in range(int(input())):
	(A, B) = inparr()
	gcdd = gcd(A, B)
	print(A - gcdd)


from functools import reduce
import math

def vout(v):
	return ' '.join(map(str, v))

def vin(datatype):
	return list(map(datatype, input().split()))

def Filter(a, b):
	return list(filter(a, b))

def Map(a, b):
	return list(map(a, b))

def Reduce(a, b):
	return list(reduce(a, b))

def main(is_testCases=True):
	testCases = 1
	if is_testCases:
		testCases = int(input())
	for _ in range(testCases):
		(a, b) = vin(int)
		print(a - math.gcd(a, b))
main()


import math
for agsdjsdkfhfk in range(int(input())):
	(f, k) = map(int, input().split())
	print(f - math.gcd(f, k))


from math import gcd
x = int(input())
for i in range(x):
	l = list(map(int, input().split()))
	lcm = l[0]
	gcd1 = gcd(l[0], l[1])
	print(lcm - gcd1)


from math import gcd
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	print(a - gcd(a, b))


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

	def gcd(a, b):
		if b == 0:
			return a
		else:
			return gcd(b, a % b)
	c = gcd(a, b)
	print(a - c)


import math
t = int(input())
for _ in range(t):
	(A, B) = map(int, input().split())
	print(A - math.gcd(B, A))


import math
t = int(input())
while t:
	(a, b) = map(int, input().split())
	print(a - math.gcd(a, b))
	t -= 1


from math import sqrt, ceil, floor, gcd, log2
import sys
from sys import stdin, stdout
from collections import Counter, defaultdict, OrderedDict, deque
from itertools import combinations, groupby
from time import time
from heapq import heappop, heappush, heapify
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	print(n - gcd(n, m))


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
for i in range(int(input())):
	(a, b) = map(int, input().split(' '))
	number = gcd(a, b)
	print(a - number)


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	x = gcd(a, b)
	print(a - x)


def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	x = gcd(a, b)
	print(a - x)


import math

def solution(a, b):
	return a - math.gcd(a, b)

def main():
	T = int(input())
	cases = []
	for _ in range(T):
		(a, b) = list(map(int, input().split()))
		cases.append((a, b))
	for case in cases:
		(a, b) = case
		print(solution(a, b))
main()


import math as m
t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	if a == b:
		print(0)
	elif a > b:
		x = m.gcd(a, b)
		print(a - x)
	else:
		x = m.gcd(a, b)
		if x == 1:
			print(a - 1)
		elif x == a:
			print(0)
		else:
			print(a - x)


from math import *
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	g = gcd(x, y)
	print(x - g)


from math import *

def solve(a, b):
	if a % b == 0:
		return a - b
	if b % a == 0:
		return 0
	return a - gcd(a, b)
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	print(solve(a, b))


def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	print(a - gcd(a, b))


def LCM(a, x):
	return abs(a * x) // GCD(a, x)

def GCD(b, x):
	while x:
		(b, x) = (x, b % x)
	return abs(b)
t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split())
	x = GCD(a, b)
	print(a - x)


import math

def LCM(a, x):
	return abs(a * x) // GCD(a, x)

def GCD(x, y):
	while y:
		(x, y) = (y, x % y)
	return abs(x)
t = int(input())
while t:
	t -= 1
	(a, b) = map(int, input().split())
	x = GCD(a, b)
	print(a - x)


from math import gcd

def main():
	T = int(input())
	for _ in range(T):
		(A, B) = map(int, input().split())
		print(A - gcd(B, A))
main()


def lcm(x, y):
	if x > y:
		(x, y) = (y, x)
	multi = 1
	t = y
	while True:
		if y % x == 0:
			break
		multi += 1
		y = t * multi
	return y

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return abs(x)
t = int(input())
while t != 0:
	s = list(map(int, input().split()))
	(a, b) = (s[0], s[1])
	print(a - gcd(a, b))
	t += -1


from math import *
for I in range(int(input())):
	(x, y) = list(map(int, input().split()))
	print(x - gcd(x, y))


import math
t = int(input())
for i in range(t):
	(a, x) = map(int, input().split())
	print(a - math.gcd(a, x))


from math import gcd
for i in ' ' * int(input()):
	(x, y) = map(int, input().split())
	print(x - gcd(x, y))


import math
t = int(input())
for i in range(t):
	l = input()
	l = l.split()
	a = int(l[0])
	b = int(l[1])
	j = 2
	k = math.gcd(b, a)
	print(a - k)


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
t = int(input())
for i in range(t):
	l = input()
	l = l.split()
	a = int(l[0])
	b = int(l[1])
	j = 2
	k = gcd(b, a)
	print(a - k)


import random
import math
from collections import defaultdict, Counter, deque, OrderedDict
from heapq import heapify, heappush, heappop
from functools import lru_cache
from bisect import bisect_left, bisect_right
import sys
input = lambda : sys.stdin.readline().strip()

class SegmentTree:

	def __init__(self, arr, func=lambda x, y: x + y, defaultvalue=0):
		self.n = len(arr)
		self.segmentTree = [0] * self.n + arr
		self.func = func
		self.defaultvalue = defaultvalue
		self.buildSegmentTree(arr)

	def buildSegmentTree(self, arr):
		for i in range(self.n - 1, 0, -1):
			self.segmentTree[i] = self.func(self.segmentTree[2 * i], self.segmentTree[2 * i + 1])

	def query(self, l, r):
		l += self.n
		r += self.n
		res = self.defaultvalue
		while l < r:
			if l & 1:
				res = self.func(res, self.segmentTree[l])
				l += 1
			l >>= 1
			if r & 1:
				r -= 1
				res = self.func(res, self.segmentTree[r])
			r >>= 1
		return res

	def update(self, i, value):
		i += self.n
		self.segmentTree[i] = value
		while i > 1:
			i >>= 1
			self.segmentTree[i] = self.func(self.segmentTree[2 * i], self.segmentTree[2 * i + 1])

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = list(range(n))

	def find(self, x):
		if self.parents[x] == x:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x != y:
			self.parents[x] = y
dire = [0, 1, 0, -1, 0]

def is_prime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def case(t):
	print('Case #{}:'.format(t), end=' ')
RANDOM = random.randrange(2 ** 62)

def Wrapper(x):
	return x ^ RANDOM

def solve():
	(a, b) = map(int, input().split())
	print(a - math.gcd(b, a))
for t in range(int(input())):
	solve()


import math
t = int(input())
for i in range(t):
	(x, y) = input().split()
	x = int(x)
	y = int(y)
	hcf = math.gcd(x, y)
	print(x - hcf)


def gcd(m, n):
	(a, b) = (max(m, n), min(m, n))
	if a % b == 0:
		return b
	else:
		return gcd(b, a % b)
T = int(input())
while T != 0:
	(a, b) = list(map(int, input().split()))
	x = gcd(a, b)
	lcm = a // gcd(a, x) * x
	g = gcd(b, x)
	print(lcm - g)
	T -= 1


import math

def ans(arr):
	return arr[0] - math.gcd(arr[0], arr[1])
test_cases = int(input())
while test_cases != 0:
	d = list(map(int, input().split()))
	print(ans(d))
	test_cases -= 1