Martha is interviewing at Subway. One of the rounds of the interview requires her to cut a bread of size $l\times b$ into smaller identical pieces such that each piece is a square having maximum possible side length with no left over piece of bread.

Input Format

The first line contains an integer $\mathbf{T}$. $\mathbf{T}$ lines follow. Each line contains two space separated integers $\boldsymbol{l}$ and $\boldsymbol{b}$ which denote length and breadth of the bread. 

Constraints

$1\leq T\leq1000$
$1\leq l,b\leq1000$

Output Format

$\mathbf{T}$ lines, each containing an integer that denotes the number of squares of maximum size, when the bread is cut as per the given condition.

Sample Input 0
2
2 2
6 9

Sample Output 0
1
6

Explanation 0

The 1^{st} testcase has a bread whose original dimensions are $2\times2$, the bread is uncut and is a square. Hence the answer is 1. 

The 2^{nd} testcase has a bread of size $6\times9$. We can cut it into 54 squares of size $1\times1$, 6 of size $3\times3$. For other sizes we will have leftovers. Hence, the number of squares of maximum size that can be cut is 6.

Source: hackerrank | Difficulty: EASY
Tags: Mathematics


Solutions:
def maximum_squares(l, b):
	if l > b:
		x = b
	else:
		x = l
	GCF = 0
	for i in range(1, x + 1):
		if l % i == 0 and b % i == 0:
			GCF = i
	print(int(l * b / (GCF * GCF)))
num_tests = int(input())
for i in range(num_tests):
	line = input()
	numbers = line.split()
	length = int(numbers[0])
	breadth = int(numbers[1])
	maximum_squares(length, breadth)


import sys

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
n = int(sys.stdin.readline())
for i in range(0, n):
	input = sys.stdin.readline().split(' ')
	l = int(input[0])
	b = int(input[1])
	side = gcd(l, b)
	print(int(l * b / (side * side)))


def num_max_squares(l, b):
	max_square_side = min(l, b)
	bread_area = l * b
	i = max_square_side
	while i > 0:
		piece_area = i * i
		if bread_area % piece_area == 0 and l % i == 0 and (b % i == 0):
			return int(bread_area / piece_area)
		i -= 1

def main():
	num_test_cases = int(input())
	result = []
	for i in range(num_test_cases):
		input_string = input().split(' ')
		bread_length = int(input_string[0])
		bread_breadth = int(input_string[1])
		num_squares = num_max_squares(bread_length, bread_breadth)
		result.append(num_squares)
	for i in range(len(result)):
		print(result[i])
main()


import sys
from fractions import gcd
sys.stdin.readline()
for line in sys.stdin:
	[b, l] = [int(s) for s in line.split()]
	area = b * l
	largest_square_size = gcd(b, l) ** 2
	print(area // largest_square_size)


import sys
import itertools
import collections
import fractions
t = int(sys.stdin.readline())
for case in range(t):
	(l, b) = map(int, sys.stdin.readline().rstrip('\n').split())
	g = fractions.gcd(l, b)
	print(int(l / g * (b / g)))


def gcd(a, b):
	(a, b) = (max(a, b), min(a, b))
	if b == 0:
		return a
	return gcd(b, a % b)
T = int(input())
for i in range(T):
	inp = input().split()
	(x, y) = (int(inp[0]), int(inp[1]))
	g = gcd(x, y)
	(x, y) = (x // g, y // g)
	print(x * y)


from fractions import gcd
i = int(input())
challenge = []
for j in range(i):
	(x, y) = map(int, input().split())
	common_divisor = gcd(x, y)
	print(x * y // common_divisor ** 2)


from fractions import gcd
import sys

def numpieces(w, h):
	div = gcd(w, h)
	return w // div * h // div
N = int(sys.stdin.readline())
for n in range(N):
	[w, h] = [int(i) for i in sys.stdin.readline().split()]
	print(numpieces(w, h))


def main():
	num_tests = int(input())
	while num_tests:
		num_tests -= 1
		(length, breadth) = [int(x) for x in input().split()]
		square_size = min(length, breadth)
		while square_size:
			if length % square_size == 0 and breadth % square_size == 0:
				break
			square_size -= 1
		square_size = length // square_size * (breadth // square_size)
		print(square_size)
main()


import sys
data = sys.stdin.readlines()
numOfLines = int(data[0].strip('\n'))
for i in range(1, numOfLines + 1):
	case = data[i].split()
	lower = int(min(case))
	for j in range(lower, 0, -1):
		length = int(case[0])
		breadth = int(case[1])
		if length % j == 0 and breadth % j == 0:
			print(int(breadth * length / j ** 2))
			break


import sys
breads = []
count = 0
for i in sys.stdin.readlines():
	if count != 0:
		breads.append(i.rsplit())
	count += 1
for i in breads:
	x = 1
	size = []
	l = int(i[0])
	b = int(i[1])
	area = l * b
	while x <= l or x <= b:
		if area % x ** 2 == 0 and l % x == 0 and (b % x == 0):
			size.append([x, area / x ** 2])
		x += 1
	print(int(size[-1][1]))


casos = int(input())
for j in range(0, casos):
	(l, b) = [int(v) for v in input().split(' ')]
	res = 0
	if l < b:
		mi = l
		ma = b
	else:
		mi = b
		ma = l
	for i in range(1, mi + 1):
		aux = divmod(l * b, i * i)
		if aux[1] == 0 and ma // i * (mi // i) == aux[0]:
			res = aux[0]
	print(res)


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

def numSquares(gcd, l, b):
	return l * b // (gcd * gcd)

def main():
	T = input()
	answers = []
	for test in range(int(T)):
		line = input()
		line = line.split()
		(l, b) = (int(line[0]), int(line[1]))
		if l < b:
			(l, b) = (b, l)
		gcd = findGCD(l, b)
		s = numSquares(gcd, l, b)
		answers.append(s)
	while answers != []:
		print(answers[0])
		answers.pop(0)
main()


import fractions
n = int(input())
for i in range(n):
	data = input()
	data = data.split()
	a = int(data[0])
	b = int(data[1])
	print(int(a * b / fractions.gcd(a, b) ** 2))


def gcd(a, b):
	while b != 0:
		(a, b) = (b, a % b)
	return a
num_tests = int(input())
for i in range(num_tests):
	q = [int(x) for x in input().split()]
	(l, b) = (q[0], q[1])
	factor = gcd(l, b)
	print(l * b // factor ** 2)


def numSquares(length, bredth, size):
	if length % size == 0 and bredth % size == 0:
		return length // size * (bredth // size)
	return 0

def optSizeCount(length, bredth):
	maxSize = min(length, bredth)
	optCount = 0
	for i in range(maxSize):
		count = numSquares(length, bredth, i + 1)
		if count > 0:
			optCount = count
	return optCount
tests = int(input().strip())
for i in range(tests):
	dim = [int(i) for i in input().strip().split()]
	print(optSizeCount(dim[0], dim[1]))


def factors(n):
	facts = []
	for i in range(1, n + 1):
		if n % i == 0:
			facts.append(i)
	return facts

def gcd(a, b):
	greatest = 1
	if a < b:
		(a, b) = (b, a)
	elif a == b:
		return a
	fb = factors(b)
	fa = factors(a)
	for each in sorted(fa, reverse=True):
		if each in fb:
			return each
T = int(input())
for test_case in range(T):
	(l, b) = map(int, input().split())
	if l == b:
		print(1)
	else:
		print(int(l * b / gcd(l, b) ** 2))


c = int(input())

def gcd(a, b):
	if a % b == 0:
		return b
	elif a < b:
		return gcd(b, a)
	else:
		return gcd(b, a % b)
for i in range(c):
	(a, b) = input().strip().split()
	(a, b) = (int(a), int(b))
	k = gcd(a, b) ** 2
	print(a * b // k)


a = input()
inp = []
rez = []
for i in range(int(a)):
	inp.append(input())
for j in range(len(inp)):
	tmp = inp[j].split(' ')
	tmp1 = int(tmp[0])
	tmp2 = int(tmp[1])
	if tmp1 == tmp2:
		rez.append(1)
	else:
		min_side = min(tmp1, tmp2)
		tmp_rez = ''
		for k in range(1, int(min_side) + 1):
			if tmp1 % k == 0 and tmp2 % k == 0:
				tmp_rez = tmp1 // k * (tmp2 // k)
		rez.append(tmp_rez)
for r in rez:
	print(r)


import sys
import math

def getDimensions():
	lines = []
	dimensions = []
	for line in sys.stdin:
		lines.append(line)
	lines.pop(0)
	for line in lines:
		dimensions.append(list(map(int, line.split())))
	return dimensions

def calcArea(lenghts):
	return lenghts[0] * lenghts[1]

def getDivisors(num):
	divs = []
	for i in range(1, 1 + round(math.sqrt(num))):
		if num % i == 0:
			if isSquared(i):
				divs.append(i)
			if i != num / i:
				if isSquared(num / i):
					divs.append(num // i)
	return sorted(divs)

def isSquared(num):
	return math.sqrt(num) == int(math.sqrt(num))

def isDivisor(a, b, num):
	return a % num == 0 and b % num == 0
area = []
divisors = []
dimensions = getDimensions()
for lenghts in dimensions:
	area.append(calcArea(lenghts))
for elem in area:
	divisors.append(getDivisors(elem))
positive = []
for i in range(len(dimensions)):
	for div in divisors[i]:
		if isDivisor(dimensions[i][0], dimensions[i][1], math.sqrt(div)):
			positive.append(area[i] // div)
	print(min(positive))
	positive = []


t = int(input())
while t:
	s = input()
	(l, b) = [int(i) for i in s.split(' ')]
	i = 2
	(x, y) = (l, b)
	while i <= l and i <= b:
		while x % i == 0 and y % i == 0:
			x = x / i
			y = y / i
		i += 1
	t -= 1
	print(int(x * y))


def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)
t = int(input())
for i in range(t):
	c = input().split()
	a = int(c[0])
	b = int(c[1])
	highestFactor = gcd(a, b)
	print(int(a / highestFactor * (b / highestFactor)))


import sys
for line in sys.stdin.readlines()[1:]:
	[l, b] = map(float, line.split(' '))
	i = 1
	while b % (l / i) != 0:
		i += 1
	print(int(i * b / (l / i)))


import re

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
N = int(input())
regexp = re.compile('[0-9]+')
for i in range(N):
	line = input()
	tokens = regexp.findall(line)
	l = int(tokens[0])
	b = int(tokens[1])
	g = gcd(l, b)
	print(l // g * b // g)


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
for t in range(int(input())):
	inp = input().split()
	l = int(inp[0])
	b = int(inp[1])
	g = gcd(l, b)
	ans = l * b / g ** 2
	print(int(ans))


def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
T = int(input())
while T:
	T = T - 1
	(l, b) = input().split()
	l = int(l)
	b = int(b)
	g = gcd(l, b)
	x = l // g
	y = b // g
	n = x * y
	print(n)


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

def main():
	t = eval(input())
	for i in range(t):
		[a, b] = input().split()
		[a, b] = [int(a), int(b)]
		g = gcd(a, b)
		print(a * b // (g * g))
main()


from fractions import gcd

def f(a, b):
	g = gcd(a, b)
	return a // g * (b // g)
for _ in range(int(input())):
	print(f(*[int(i) for i in input().split()]))


def gcd(a, b):
	if a > b:
		(a, b) = (b, a)
	while a > 0:
		(a, b) = (b % a, a)
	return b
T = int(input())
for _ in range(T):
	(l, b) = (int(_) for _ in input().split())
	print(l * b // gcd(l, b) ** 2)


tests = int(input())
pairs = []
maxv = 0
for i in range(0, tests):
	cur = str(input()).split(' ')
	cur[0] = int(cur[0])
	cur[1] = int(cur[1])
	if cur[0] > maxv:
		maxv = cur[0]
	if cur[1] > maxv:
		maxv = cur[1]
	pairs.append(cur)
maxp = maxv
primes = [2]
prim = 3
while prim <= maxp:
	pri = True
	for j in primes:
		if prim % j == 0:
			pri = False
			break
	if pri:
		primes.append(prim)
	prim += 2
for i in range(0, tests):
	tw = pairs[i][0]
	tl = pairs[i][1]
	for j in primes:
		while tw % j == 0 and tl % j == 0:
			tw /= j
			tl /= j
	print(int(tw * tl))


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
t = int(input())
for case_t in range(t):
	(l, b) = [int(item) for item in input().strip().split()]
	side = gcd(l, b)
	print(l // side * b // side)


from fractions import gcd
for case in range(int(input())):
	(a, b) = map(int, input().split())
	print(a * b // gcd(a, b) ** 2)


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
for t in range(int(input())):
	(w, h) = [int(i) for i in input().split()]
	gcdwh = gcd(w, h)
	print(w * h // gcdwh // gcdwh)


def findnumber(a, b):
	product = a * b
	solution = 1
	if a < b:
		low = a
		high = b
	elif b < a:
		temp = a
		low = b
		high = temp
	elif a == b:
		low = a
		high = b
	i = 1
	while i <= low:
		if a % i == 0 and b % i == 0 and (high != low):
			solution = int(product / (i * i))
		elif high == low:
			solution = 1
		i += 1
	print(solution)
testCaseNum = int(input())
testInWork = 0
while testInWork < testCaseNum:
	the_string = input()
	(num1, num2) = the_string.split()
	findnumber(int(num1), int(num2))
	testInWork += 1


from fractions import gcd
lines = int(input())
for i in range(lines):
	actualLine = input().split(' ')
	x = int(actualLine[0])
	y = int(actualLine[1])
	divisor = gcd(x, y)
	print(int(x / divisor * (y / divisor)))


def gcd(a, b):
	(big_num, small_num) = (max(a, b), min(a, b))
	c = big_num % small_num
	if c != 0:
		small_num = gcd(small_num, c)
	return small_num

def main():
	number_of_test_cases = int(input())
	for i in range(number_of_test_cases):
		(l, b) = list(map(int, input().strip().split(' ')))
		g = gcd(max(l, b), min(l, b))
		res = int(l / g * b / g)
		print(res)
main()


import operator

def get_gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def main():
	dimensions = [int(n) for n in input().split()]
	gcd = get_gcd(*dimensions)
	return operator.mul(*(int(dimension / gcd) for dimension in dimensions))
cases = int(input())
for _ in range(cases):
	print(main())


T = int(input())
for t in range(T):
	d = input().split()
	l = int(d[0])
	b = int(d[1])
	area = l * b
	x = max(l, b)
	out = 0
	squares = [a for a in range(1, x + 1)]
	squares.reverse()
	for s in squares:
		if l % s == 0 and b % s == 0:
			out = area // s ** 2
			break
	print(out)


def gcd(a, b):
	if b > a:
		(a, b) = (b, a)
	rest = a % b
	if rest == 0:
		return b
	return gcd(b, rest)
tests = int(input())
for x in range(tests):
	(w, h) = (int(n) for n in input().split())
	s = gcd(w, h)
	result = w * h / (s * s)
	print(int(result))


def hcf(i, j):
	m = min(i, j)
	for k in range(0, m + 1):
		if i % (m - k) == 0 and j % (m - k) == 0:
			res = m - k
			break
	return res
a = int(input())
for i in range(0, a):
	x = list(map(int, input().split()))
	y = hcf(x[0], x[1])
	print(int(x[0] * x[1] / y ** 2))


for i in range(int(input())):
	(l, b) = map(int, input().split())
	(x, y) = (max(l, b), min(l, b))
	while y != 0:
		(x, y) = (y, x % y)
	print(str(l * b // x ** 2))


def gcd(a, b):
	if a == b:
		return a
	elif a > b:
		return gcd(a - b, b)
	else:
		return gcd(a, b - a)
for i in range(int(input())):
	(a, b) = tuple(map(int, input().split()))
	gdiv = gcd(a, b)
	print(a * b // gdiv ** 2)


from fractions import gcd
for t in range(int(input())):
	(a, b) = map(int, input().split())
	print(a * b // gcd(a, b) ** 2)


from fractions import gcd
for i in range(int(input())):
	(a, b) = [int(j) for j in input().split(' ')]
	print(int(a * b / gcd(a, b) ** 2))


def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def main():
	t = int(input())
	for i in range(t):
		(L, B) = (int(x) for x in input().split())
		edgeLength = gcd(L, B)
		print(L * B // edgeLength ** 2)
main()


def GCF(a, b):
	while a != 1 and b != 1:
		if a == 0:
			return b
		elif b == 0:
			return a
		elif a >= b:
			a = a % b
		elif b > a:
			b = b % a
	return 1
T = int(input())
for i in range(T):
	k = input()
	x = k.split(' ')
	a = int(x[0])
	b = int(x[1])
	print(int(a * b / GCF(a, b) ** 2))


def main():
	for case in range(int(input())):
		(l, b) = [int(x) for x in str(input()).split()]
		print(check(l, b))

def check(l, b):
	if l == b:
		return 1
	for i in range(1, min(l, b) + 1)[::-1]:
		n = num_square_size(l, b, i)
		if n > 0:
			return n
	return 0

def num_square_size(l, b, i):
	q = l % i == 0
	w = b % i == 0
	return int(l / i * (b / i)) if q and w else 0
main()


from fractions import gcd
import sys
inp = sys.stdin.readlines()
T = int(inp[0])
for i in range(1, T + 1):
	f = int(inp[i].split(' ')[0])
	s = int(inp[i].split(' ')[1])
	g = gcd(f, s)
	print(int(f / g) * int(s / g))


T = int(input(''))
while T > 0:
	x = input('')
	lis = x.split()
	lis = list(map(int, lis))
	if lis[0] == lis[1]:
		print(1)
	else:
		l = lis[0]
		b = lis[1]
		total = l * b
		lis_l = []
		i = 2
		while i <= l:
			if l % i == 0:
				lis_l.append(i)
				l //= i
				i -= 1
			i += 1
		lis_b = []
		i = 2
		while i <= b:
			if b % i == 0:
				lis_b.append(i)
				b //= i
				i -= 1
			i += 1
		lis_com = []
		for val in lis_l:
			j = 0
			while j <= len(lis_b) - 1:
				if val == lis_b[j]:
					lis_com.append(val)
					del lis_b[j]
					break
				j += 1
		s = 1
		for value in lis_com:
			s *= value
		print(total // s ** 2)
	T -= 1


T = int(input())
for i in range(T):
	(l, b) = [int(i) for i in input().split()]
	bound = min(l, b)
	m = 1
	for i in range(1, bound + 1):
		if l * b % i ** 2 == 0 and i > m and (l % i == 0) and (b % i == 0):
			m = i
	print(int(l * b / m ** 2))


from fractions import gcd
for t in range(int(input())):
	(a, b) = [int(a) for a in input().split()]
	c = gcd(a, b)
	print(int(a / c * (b / c)))


import math
T = input()
ti = int(T)
while ti > 0:
	(ai, bi) = input().split()
	a = int(ai)
	b = int(bi)
	i = 1
	best = 1
	while i <= math.ceil(math.sqrt(a * b)):
		if a % i is 0 and b % i is 0:
			best = a * b / i ** 2
		i += 1
	ti -= 1
	print(int(best))


from fractions import gcd

def func(x, y):
	a = x // gcd(x, y)
	b = y // gcd(x, y)
	return a * b
t = int(input())
for _ in range(t):
	print(func(*[int(x) for x in input().split()]))


from fractions import gcd
cases = int(input())
for _ in range(cases):
	(l, w) = [int(i) for i in input().split()]
	denom = gcd(l, w)
	print(l // denom * (w // denom))


import fractions
n = int(input())
for i in range(n):
	x = input()
	x = x.split()
	a = int(x[0])
	b = int(x[1])
	squares = 0
	size = 0
	gcd = fractions.gcd(a, b)
	total = a * b / (gcd * gcd)
	print(int(total))


test = int(input())

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


def maxSize(l, b):
	for side in range(1, min(l, b) + 1):
		ll = l // side
		bb = b // side
		if ll != l / side or bb != b / side or ll == 0 or (bb == 0):
			continue
		else:
			amount = ll * bb
	return amount
for _ in range(int(input())):
	(l, b) = input().split(' ')
	print(maxSize(int(l), int(b)))


T = int(input())

def gcd(a, b):
	mn = min(a, b)
	mx = max(a, b)
	while mn != 0:
		tmp = mx % mn
		mx = mn
		mn = tmp
	return mx
for i in range(T):
	(a, b) = [int(s) for s in input().split()]
	print(a * b // gcd(a, b) ** 2)


def gcd(a, b):
	while b != 0:
		a %= b
		(a, b) = (b, a)
	return a
for _ in range(int(input())):
	(l, b) = map(int, input().strip().split())
	print(int(l * b / gcd(l, b) ** 2))


def largest_square(l, b):
	A = l * b
	N = []
	Nf = []
	n = 1
	a = 1
	while a < A:
		a = n * n
		N.append(n)
		n += 1
	for i in range(len(N)):
		if l % N[i] == 0 and b % N[i] == 0:
			Nf.append(N[i])
	Nf.sort()
	print(int(A / (Nf[-1] * Nf[-1])))
T = int(input())
for i in range(T):
	li = [int(i) for i in input().strip().split()]
	largest_square(li[0], li[1])


from fractions import gcd
t = int(input())
for i in range(t):
	(l, w) = list(map(int, input().split(' ')))
	square_size = gcd(l, w) ** 2
	bread_size = l * w
	squares = int(bread_size / square_size)
	print(squares)


def gcd(a, b):
	(a, b) = (a, b) if a > b else (b, a)
	while b > 0:
		(a, b) = (b, a % b)
	return a
t = int(input())
for _ in range(t):
	(l, b) = [int(x) for x in input().split()]
	ans = gcd(l, b)
	print(l * b // ans ** 2)


from fractions import gcd
t = int(input())
for _ in range(t):
	(l, b) = map(int, input().split())
	print(int(l * b / gcd(l, b) ** 2))


def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
t = int(input())
for _ in range(t):
	(n, m) = [int(_) for _ in input().split()]
	print(m * n // gcd(m, n) ** 2)


for _ in range(int(input().strip())):
	(l, b) = map(int, input().strip().split(' '))
	res = 1
	for i in range(1, min(l, b) + 1):
		if (l / i).is_integer() and (b / i).is_integer():
			res = i
	print(int(l * b / res / res))


from math import sqrt

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
for _ in range(int(input())):
	l = input().split()
	(x, y) = (int(l[0]), int(l[1]))
	print(x * y // gcd(x, y) ** 2)


from fractions import gcd

def restaurant(l, b):
	a = gcd(l, b)
	return int(l / a * (b / a))
T = int(input())
for i in range(T):
	(l, b) = (int(x) for x in input().split())
	print(restaurant(l, b))


def gcd(nums):
	if nums[1] == 0:
		return nums[0]
	else:
		return gcd([nums[1], nums[0] % nums[1]])
for _ in range(int(input())):
	(length, width) = [int(x) for x in input().split(' ')]
	print(length * width // gcd([length, width]) ** 2)


import math
t = int(input())
while t:
	size = input().split()
	l = int(size[0])
	b = int(size[1])
	totalSize = l * b
	answer = totalSize
	for i in range(1, max(l, b) + 1):
		tmp = totalSize / (i * i)
		if l % i == 0 and b % i == 0:
			answer = tmp
	print(int(answer))
	t -= 1


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


from fractions import gcd
T = int(input())
for i in range(0, T):
	(x, y) = map(lambda y: int(y), input().split())
	the_gcd = gcd(x, y)
	number = int(x / the_gcd * (y / the_gcd))
	print(number)


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

def func(lis):
	size = gcd(lis[0], lis[1])
	return lis[0] // size * (lis[1] // size)
for _ in range(int(input())):
	print(func([int(x) for x in input().split()]))


from collections import namedtuple
case_count = int(input())
Case = namedtuple('Case', ['l', 'b'])
cases = [Case._make((int(i) for i in input().split())) for _ in range(case_count)]

def greatest_common_divider(a, b):
	if b == 0:
		return a
	return greatest_common_divider(b, a % b)
for case in cases:
	gcd = greatest_common_divider(case.l, case.b)
	print(int(case.l * case.b / gcd ** 2))


def mcd(a, b):
	if b == 0:
		return a
	else:
		return mcd(b, a % b)
for _ in range(int(input())):
	(r, c) = map(int, input().split())
	m = mcd(r, c)
	print(r // m * (c // m))


from fractions import gcd
for x in range(int(input())):
	(a, b) = map(int, input().split())
	c = gcd(a, b)
	print(int(a / c * (b / c)))


import fractions, sys
T = int(sys.stdin.readline())
for _ in range(T):
	(l, b) = list(map(int, sys.stdin.readline().split()))
	print(l * b // fractions.gcd(l, b) ** 2)


num_cases = int(input())
for n in range(0, num_cases):
	inp = input().split()
	l = int(inp[0])
	b = int(inp[1])
	num_pc = 1
	for i in range(1, min(l, b) + 1):
		if l % i == 0 and b % i == 0:
			num_pc = i
	print(int(l * b / num_pc ** 2))


def max_size(x, y):
	max_length = min(x, y)
	max_squares = 0
	for i in range(1, max_length + 1):
		if x % i == 0 and y % i == 0:
			max_squares = x * y / (i * i)
	return int(max_squares)

def main():
	n = int(input())
	for i in range(n):
		(x, y) = [int(x) for x in input().split()]
		print(max_size(x, y))
main()


for x in range(int(input())):
	[l, b] = map(lambda z: int(z), input().split(' '))
	m = min(l, b)
	for i in reversed(range(1, m + 1)):
		if l % i == 0 and b % i == 0:
			print(int(l * b / (i * i)))
			break


from fractions import gcd
numcases = int(input())
for _ in range(numcases):
	(n, m) = [int(x) for x in input().split(' ')]
	area = n * m
	print(area // pow(gcd(n, m), 2))


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

def min_squares(l, r):
	if l == r:
		return 1
	cd = gcd(l, r)
	return l // cd * (r // cd)
t = int(input())
for _ in range(t):
	(l, r) = [int(el) for el in input().split()]
	print(min_squares(l, r))


from fractions import gcd
t = int(input())
while t > 0:
	s = str(input())
	lt = s.split()
	y = int(lt[0]) * int(lt[1])
	gc = gcd(int(lt[0]), int(lt[1]))
	ans = y / (gc * gc)
	print(int(ans))
	t = t - 1


import math
T = int(input())
for i in range(0, T):
	lists = [int(i) for i in input().split()]
	l = lists[0]
	b = lists[1]
	if l >= b:
		for i in range(1, b + 1):
			if l % i == 0 and b % i == 0:
				maxi = i
	if b > l:
		for i in range(1, l + 1):
			if l % i == 0 and b % i == 0:
				maxi = i
	print(int(l * b / (maxi * maxi)))


def gcd(x, y):
	if y == 0:
		return x
	return gcd(y, x % y)
for x in range(int(input())):
	(x, y) = [int(x) for x in input().split()]
	t = gcd(x, y)
	print(x * y // (t * t))


numtest = int(input())
for z in range(numtest):
	(b, l) = input().split()
	b = int(b)
	l = int(l)
	m = min(b, l)
	ans = 0
	for i in range(1, m + 1):
		if b % i == 0 and l % i == 0:
			ans = int(b * l / (i * i))
	print(ans)


def get_area(l, b):
	return l * b

def squares(l, b):
	area = get_area(l, b)
	n = 0
	a = 1
	while True:
		max_area_square = a * a
		if max_area_square > area:
			return n
		if area % max_area_square == 0 and l % a == 0 and (b % a == 0):
			n = area // max_area_square
		a += 1
testcases = int(input())
for _ in range(testcases):
	(l, b) = [int(x) for x in input().split()]
	n = squares(l, b)
	print(n)


a = int(input())
for i in range(a):
	c = input().split(' ')
	(c[0], c[1]) = (int(c[0]), int(c[1]))
	if c[0] < c[1]:
		x = c[0]
	else:
		x = c[1]
	max = 1.0
	for i in range(1, x + 1):
		if (c[0] % i or c[1] % i or c[1] * c[0] % (i * i)) == 0:
			max = c[0] * c[1] / (i * i)
	print(int(max))


def gcd(a, b):
	while b != 0:
		(a, b) = (b, a % b)
	return abs(a)
t = int(input())
m = []
for i in range(t):
	m.append([int(x) for x in input().split()])
for i in range(t):
	a = gcd(m[i][0], m[i][1])
	a = m[i][0] * m[i][1] / (a * a)
	print(int(a))


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	dimension = a * b
	size = 10000000
	for i in range(1, min(a, b) + 1):
		square = i ** 2
		if a % i == 0 and b % i == 0 and (dimension % square == 0):
			size = min(size, dimension // square)
	print(size)


def gcd(x, y):
	if y == 0:
		return x
	else:
		return gcd(y, x % y)
for _ in range(int(input())):
	(l, m) = [int(i) for i in input().split()]
	a = gcd(l, m)
	print(int(l / a) * int(m / a))


def pgcd(a, b):
	if b > a:
		return pgcd(b, a)
	elif a == b:
		return a
	else:
		r = a % b
		if r == 0:
			return b
		else:
			return pgcd(b, r)

def main():
	t = int(input())
	for x in range(t):
		(b, l) = map(int, input().split())
		p = pgcd(b, l)
		print(b // p * (l // p))
main()


T = int(input())
for i in range(T):
	empty = []
	crsstn = input()
	crsstnl = crsstn.split()
	if int(crsstnl[0]) < int(crsstnl[1]):
		min = int(crsstnl[0])
	else:
		min = int(crsstnl[1])
	for j in range(1, min + 1):
		if int(crsstnl[0]) % j == 0 and int(crsstnl[1]) % j == 0:
			empty.append(j)
	print(int(int(crsstnl[0]) * int(crsstnl[1]) / max(empty) ** 2))


from fractions import gcd

def slice_bread(l, b):
	max_even_slice = gcd(l, b)
	bread_area = l * b
	max_even_slice_area = max_even_slice ** 2
	return int(bread_area / max_even_slice_area)
num_cases = int(input())
cases = (list(map(int, input().strip().split(' '))) for _ in range(num_cases))
print(*list(map(lambda d: slice_bread(d[0], d[1]), cases)), sep='\n')


def gcd(a, b):
	if a < b:
		return gcd(b, a)
	elif a % b == 0:
		return b
	else:
		return gcd(b, a % b)
T = int(input())
for i in range(T):
	(l, b) = input().split(' ')
	(l, b) = (int(l), int(b))
	size = gcd(l, b)
	num_squares = l // size * (b // size)
	print(num_squares)


from fractions import gcd
numTests = int(input())
for test in range(numTests):
	(a, b) = [int(num) for num in input().split(' ')]
	print(a * b // gcd(a, b) ** 2)


def ans(x, y, a):
	ans = 0
	for i in range(1, x + 1):
		if a % i ** 2 == 0 and y % i == 0 and (x % i == 0):
			ans = a / i ** 2
	return int(ans)
i = int(input())
while i > 0:
	(x, y) = input().split(' ')
	x = int(x)
	y = int(y)
	if x < y:
		print(ans(x, y, x * y))
	else:
		print(ans(y, x, x * y))
	i -= 1