Given two positive numbers B and C, what is the minimum positive value of A, such that A \cdot B is divisible by C.

Here, A \cdot B denotes the value obtained when A is multiplied by B. 

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

- The first line will contain an integer T - number of test cases. Then the test cases follow.
- The first and only line of each test case contains two integers B and C.

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

For each test case, output the minimum value of A such that A \cdot B is divisible by C. 

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

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

----- Sample Input 1 ------ 
2
2 4
8 12
----- Sample Output 1 ------ 
2
3
----- explanation 1 ------ 
Test case $1$: We have $B = 2$ and $C = 4$. If we choose $A = 2$, then $A \cdot B = 4$, which is divisible by $4$. Note that this is minimum positive value of $A$, such that $A \cdot B$ is divisible by $C$.

Test case $2$: We have $B = 8$ and $C = 12$. If we choose $A = 3$, then $A \cdot B = 24$, which is divisible by $12$. Note that this is minimum positive value of $A$, such that $A \cdot B$ is divisible by $C$.

Source: codechef | Difficulty: EASY
Tags: Number theory

Mathematics


Solutions:
def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
t = int(input())
for _ in range(t):
	(b, c) = map(int, input().split())
	print(c // gcd(b, c))


from math import gcd
for t in range(int(input())):
	(b, c) = map(int, input().split(' '))
	print(c // gcd(b, c))


import math
for t in range(int(input())):
	(b, c) = map(int, input().split(' '))
	if b % c == 0:
		a = 1
	elif c % b == 0:
		a = int(c / b)
	else:
		num = b // math.gcd(b, c) * c
		a = int(num / b)
	print(a)


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


from sys import stdin
from math import gcd
input = stdin.readline
for _ in range(int(input())):
	(b, c) = map(int, input().split())
	print(c // gcd(b, c))


def gcd(b, d):
	if d == 0:
		return b
	else:
		return gcd(d, b % d)
t = int(input())
for It in range(t):
	(b, d) = map(int, input().split())
	a = d / gcd(b, d)
	print(int(a))


import math as m
for _ in range(int(input())):
	(b, c) = map(int, input().split())
	print(c // m.gcd(b, c))


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


import math
T = int(input())
for i in range(T):
	(b, c) = map(int, input().split())
	ans = int(c / math.gcd(b, c))
	print(ans)


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

def get_lcm(x, y):
	lcm = x * y // compute_gcd(x, y)
	return lcm
for _ in range(int(input())):
	(b, c) = map(int, input().split())
	print(get_lcm(b, c) // b)


import math
try:
	T = int(input())
	for i in range(T):
		(B, C) = map(int, input().split())
		print(C // math.gcd(B, C))
except:
	pass


import numpy
t = int(input())
for i in range(t):
	(b, c) = map(int, input().split())
	a = numpy.lcm(b, c)
	print(a // b)


t = 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
while t > 0:
	(b, c) = map(int, input().split())
	n = lcm(b, c)
	print(n // b)
	t -= 1


import math
t = int(input())
for tc in range(t):
	(b, c) = map(int, input().split())
	n = math.gcd(b, c)
	print(c // n)


import math
t = int(input(''))
for i in range(t):
	s = list(map(int, input().split(' ')))
	a = math.gcd(s[0], s[1])
	print(s[1] // a)


t = int(input())
while t:
	t -= 1
	l = list(map(int, input().split()))

	def hcf(a, b):
		if b == 0:
			return a
		else:
			return hcf(b, a % b)
	x = hcf(l[0], l[1])
	x = l[0] * l[1] // x
	x = x // l[0]
	print(x)


import math
for i in range(int(input())):
	(b, c) = map(int, input().split())
	x = math.gcd(b, c)
	print(c // x)


import math
t = int(input())
while t > 0:
	(B, C) = map(int, input().split())
	A = C // math.gcd(B, C)
	print(A)
	t -= 1


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

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


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


import math
T = int(input())
for _ in range(T):
	(b, c) = map(int, input().split())
	d = math.gcd(b, c)
	print(c // d)


from math import *
T = int(input())
for i in range(T):
	(B, C) = map(int, input().split())
	if B >= C and B % C == 0:
		print(1)
	else:
		a = gcd(B, C)
		print(C // a)


from math import *
t = int(input())
for _ in range(t):
	n = list(map(int, input().split()))
	b = n[0]
	c = n[1]
	print(int(c / gcd(b, c)))


import math
t = int(input())
for _ in range(t):
	(b, c) = map(int, input().split(' '))
	myGcd = math.gcd(b, c)
	a = c // myGcd
	print(a)


def hcf(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
t = int(input())
while t != 0:
	(b, c) = map(int, input().split())
	h = hcf(b, c)
	print(c // h)
	t = t - 1


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


from math import *

def call(b, c):
	print(c // gcd(b, c))
for i in range(int(input())):
	(b, c) = map(int, input().split())
	call(b, c)


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


import math as m
for i in range(int(input())):
	(a, b) = map(int, input().split())
	lcm = a * b // m.gcd(a, b)
	print(lcm // a)


from math import *
a = int(input())
for i in range(a):
	(f, g) = map(int, input().split())
	print(g // gcd(f, g))


def gcd(x, y):
	if y == 0:
		return x
	else:
		return gcd(y, x % y)
for i in range(int(input())):
	(a, b) = map(int, input().split())
	g = gcd(a, b)
	print(b // g)


import math

def find_a(b, c):
	return c // math.gcd(b, c)
for _ in range(int(input())):
	l = list(map(int, input().split()))
	(b, c) = (l[0], l[1])
	print(find_a(b, c))


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


import math
for _ in range(int(input())):
	(b, c) = map(int, input().split())
	z = b * c // math.gcd(b, c)
	print(z // b)


import math
for _ in range(int(input())):
	(b, c) = map(int, input().split())
	s = []
	i = 1
	z = b * c // math.gcd(b, c)
	print(z // b)


def hcf(x, y):
	if x == 0:
		return y
	else:
		return hcf(y % x, x)
T = int(input())
for i in range(0, T):
	(b, c) = input().split()
	b = int(b)
	c = int(c)
	res = hcf(b, c)
	a = int(c / res)
	print(a)


def computeGCD(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
for i in range(int(input())):
	(b, c) = map(int, input().split())
	a = computeGCD(b, c)
	print(c // a)


def compute_hcf(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
for _ in range(int(input())):
	(b, c) = map(int, input().split())
	hcf = compute_hcf(b, c)
	print(c // hcf)


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


from math import gcd
t = int(input())
for _ in range(t):
	line = input().split(' ')
	b = int(line[0])
	c = int(line[1])
	great = gcd(b, c)
	res = c // great
	print(res)


import math
for _ in range(int(input())):
	(b, c) = list(map(int, input().split()))
	if b % c == 0:
		print('1')
	else:
		d = math.gcd(b, c)
		print(int(c / d))