Santosh has a farm at Byteland. He has a very big family to look after.  His life takes a sudden turn and he runs into a financial crisis. After giving all the money he has in his hand, he decides to sell his plots. The speciality of his land is that it is rectangular in nature. Santosh comes to know that he will get more money if he sells square shaped plots. So keeping this in mind, he decides to divide his land into minimum possible number of square plots, such that each plot has the same area, and  the plots divide the land perfectly. He does this in order to get the maximum profit out of this.   
So your task is to find the minimum number of square plots with the same area, that can be formed out of the rectangular land, such that they divide it perfectly.

-----Input-----
- The first line of the input contains $T$, the number of test cases. Then $T$ lines follow.
- The first and only line of each test case contains two space-separated integers, $N$ and $M$, the length and the breadth of the land, respectively.

-----Output-----
For each test case, print the minimum number of square plots with equal area, such that they divide the farm land perfectly, in a new line.

-----Constraints-----
$1 \le T \le 20$
$1 \le M \le 10000$
$1 \le N \le 10000$ 

-----Sample Input:-----
2
10 15
4 6

-----SampleOutput:-----
6
6

Difficulty: EASY
Tags: Geometry

Number theory

Mathematics

Starter code:

Solutions:
def all_factors(n):
	f_list = [x for x in range(1, n // 2 + 1) if n % x == 0]
	f_list.append(n)
	return f_list
T = int(input())
for t in range(0, T):
	(N, M) = map(int, input().split())
	n_factors = all_factors(N)
	m_factors = all_factors(M)
	gcf = max(set(n_factors) & set(m_factors))
	n_plots = M * N // (gcf * gcf)
	print(n_plots)


for t in range(int(input())):
	(n, m) = map(int, input().split())
	for i in range(1, min(n, m) + 1):
		if n % i == 0 and m % i == 0:
			a = i
	print(n * m // (a * a))


import math
for tc in range(int(input())):
	(a, b) = map(int, input().split())
	area = a * b
	side = math.gcd(a, b)
	print(area // side ** 2)


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


import math
T = int(input())
for i in range(T):
	(M, N) = map(int, input().split())
	result = M * N
	print(result // math.gcd(M, N) ** 2)


for i in range(int(input())):
	(length, breadth) = map(int, input().split())
	for i in range(1, min(length, breadth) + 1):
		if length % i == 0 and breadth % i == 0:
			value = i
	print(length * breadth // (value * value))


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


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


def lcm(a, b):
	if a > b:
		greater = a
	else:
		greater = b
	while True:
		if greater % a == 0 and greater % b == 0:
			lcm = greater
			break
		greater += 1
	return lcm
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	k = lcm(n, m)
	k = k * k
	print(k // (n * m))


import math
for i in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	x = math.gcd(n, m)
	print(n // x * (m // x))


for i in range(int(input())):
	(a, b) = map(int, input().split())
	for j in range(1, min(a, b) + 1):
		if a % j == 0 and b % j == 0:
			x = j
	print(int(a * b) // (x * x))


import math
for i in range(int(input())):
	(n, m) = map(int, input().split())
	print(n * m // math.gcd(n, m) ** 2)


import math
t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	for i in range(1, min(a, b) + 1):
		if a % i == 0 and b % i == 0:
			m = i
	print(a * b // (m * m))


import math
test = int(input())
for _ in range(0, test):
	(l, b) = list(map(int, input().split()))
	num = math.gcd(l, b)
	print(l * b // num ** 2)


import math
try:
	t = int(input())
	for r in range(t):
		(n, m) = map(int, input().split())
		c = math.gcd(n, m)
		b = n * m // (c * c)
		print(b)
except:
	pass


for i in range(int(input())):
	(x, y) = map(int, input().split())
	p = x * y
	min1 = min(x, y)
	for i in range(1, min1 + 1):
		if x % i == 0 and y % i == 0:
			c = i
	print(x * y // (c * c))


import math
for i in range(int(input())):
	(n, m) = map(int, input().split())
	for j in range(1, min(n, m) + 1):
		if n % j == 0 and m % j == 0:
			k = j
	print(m * n // (k * k))


import math
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	area = n * m
	side = math.gcd(n, m)
	num_squares = area // (side * side)
	print(num_squares)


T = int(input())
for i in range(T):
	(Length, Breadth) = map(int, input().split())
	for j in range(1, min(Length, Breadth) + 1):
		if Length % j == 0 and Breadth % j == 0:
			m = j
	print(Length * Breadth // (m * m))


for i in range(int(input())):
	(N, M) = map(int, input().split())
	for j in range(1, min(N, M) + 1):
		if N % j == 0 and M % j == 0:
			a = j
	print(N * M // (a * a))


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


import math
t = int(input())
for _ in range(t):
	(N, M) = map(int, input().split())
	for j in range(1, min(N, M) + 1):
		if N % j == 0 and M % j == 0:
			s = j
	print(N * M // (s * s))


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


try:
	for _ in range(int(input())):
		(l, b) = map(int, input().split())
		area = l * b
		while b:
			(l, b) = (b, l % b)
		print(int(area / (l * l)))
except:
	pass


from math import gcd as g
for _ in range(int(input())):
	(a, b) = [int(x) for x in input().split()]
	gc = g(a, b)
	r = a // gc * (b // gc)
	print(r)


import math
for i in range(int(input())):
	(l, b) = list(map(int, input().split()))
	gcd1 = math.gcd(l, b)
	newl = l // gcd1
	new2 = b // gcd1
	print(newl * new2)


import math
for t in range(int(input())):
	(n, m) = list(map(int, input().split()))
	area = n * m
	res = math.gcd(n, m)
	res = res ** 2
	print(area // res)


import math
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	x = math.gcd(N, M)
	print(N // x * (M // x))


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


import math
T = int(input())
for i in range(T):
	(n, m) = map(int, input().split())
	side = math.gcd(n, m)
	print(int(n * m // math.pow(side, 2)))


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


t = int(input())
while t > 0:
	(n, m) = map(int, input().split())
	if n > m:
		(n, m) = (m, n)
	i = n
	while i >= 1:
		if n % i == 0 and m % i == 0:
			break
		i -= 1
	square = n * m / i ** 2
	print(int(square))
	t -= 1


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	q = n * m
	j = q
	f = []
	for i in range(min(n, m), 0, -1):
		if n % i == 0 and m % i == 0:
			j = q // (i * i)
			f.append(j)
	print(min(f))


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


import math
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	x = math.gcd(n, m)
	ans = n * m // (x * x)
	print(ans)


import math
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	hcf = math.gcd(n, m)
	ans = n * m // (hcf * hcf)
	print(ans)


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


import math
for _ in range(int(input())):
	(N, M) = [int(i) for i in input().split()]
	print(N * M // math.gcd(M, N) ** 2)


import math
t = int(input())
for tc in range(t):
	(n, m) = map(int, input().split())
	for j in range(1, min(n, m) + 1):
		if n % j == 0 and m % j == 0:
			a = j
	print(n * m // (a * a))


t = int(input())
for tc in range(t):
	(n, m) = map(int, input().split())
	for j in range(1, min(n, m) + 1):
		if n % j == 0 and m % j == 0:
			x = j
	print(n * m // (x * x))


import math
t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	x = math.gcd(n, m)
	print(n // x * m // x)


import math
t = int(input())
for i in range(t):
	(n, m) = list(map(int, input().split()))
	print(n // math.gcd(n, m) * m // math.gcd(n, m))


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


a = int(input())
for i in range(a):
	rect = input()
	rect = rect.split(' ')
	b = int(rect[0])
	l = int(rect[1])
	maxx = 1
	for i in range(1, b + 1):
		if b % i == 0 and l % i == 0:
			maxx = i
	print(l // maxx * b // maxx)


import math
t = int(input())
for i in range(t):
	(l, b) = map(int, input().split())
	area = l * b
	gcd = math.gcd(l, b)
	gcd = gcd ** 2
	print(area // gcd)


import math
n = int(input())
x = []
for i in range(0, n):
	(l, b) = list(map(int, input().split()))
	area = l * b
	g = math.gcd(l, b)
	g = g ** 2
	x.append(area // g)
for i in x:
	print(i)


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


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	area = n * m
	for i in range(1, m + 1):
		if n % i == 0 and m % i == 0:
			hcf = i
	print(area // hcf ** 2)


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


import math
t = int(input())
for i in range(t):
	(N, M) = map(int, input().split(' '))
	x = math.gcd(N, M)
	y = N * M // x ** 2
	print(y)


def compute_hcf(x, y):
	if x > y:
		smaller = y
	else:
		smaller = x
	for i in range(1, smaller + 1):
		if x % i == 0 and y % i == 0:
			hcf = i
	return hcf
for _ in range(int(input())):
	(m, n) = map(int, input().split())
	hcf = compute_hcf(m, n)
	print(m // hcf * n // hcf)


import math
for i in range(int(input())):
	(l, m) = map(int, input().split())
	nm = int(l * m / math.gcd(l, m) ** 2)
	print(nm)


import math
t = int(input())
for i in range(t):
	(a, b) = list(map(int, input().split()))
	x = math.gcd(a, b)
	m = a * b // x ** 2
	print(m)


for t in range(int(input())):
	(length, breadth) = map(int, input().split())
	area = length * breadth
	squares = 0
	for val in range(1, min(length, breadth) + 1):
		if length % val == 0 and breadth % val == 0:
			squares = val
	print(area // (squares * squares))


import math
t = int(input())
for i in range(t):
	(l, b) = map(int, input().split())
	r = l * b
	s = math.gcd(l, b)
	s = s ** 2
	print(r // s)


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


t = int(input())
for i in range(t):
	(x, y) = map(int, input().split())
	for i in range(1, min(x, y) + 1):
		if x % i == 0 and y % i == 0:
			a = i
	print(x * y // a ** 2)


for i in range(int(input())):
	(N, M) = map(int, input().split())
	for i in range(1, min(N, M) + 1):
		if N % i == 0 and M % i == 0:
			P = i
	print(N * M // (P * P))


for _ in range(int(input())):
	(m, n) = map(int, input().split())
	for j in range(1, min(m, n) + 1):
		if m % j == 0 and n % j == 0:
			k = j
	print(int(m * n / (k * k)))


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


t = int(input())

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


import math
t = int(input())
ans = list()
for i in range(t):
	n = list(map(int, input().split()))
	x = math.gcd(n[0], n[1])
	y = n[0] / x * (n[1] / x)
	ans.append(y)
for l in ans:
	print(int(l))


T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	for i in range(1, min(N, M) + 1):
		if N % i == 0 and M % i == 0:
			m = i
	print(N * M // m ** 2)