Give me Biscuit

Sunny wants to make slices of biscuit of size c * d into identical pieces.

but each piece is a square having maximum possible side length with no left over piece of biscuit.

Input Format

The first line contains an integer N.

N lines follow. Each line contains two space separated integers c and d.

which denote length and breadth of the biscuit.

Constraints

1 <= N <= 1000

1 <= c,d <= 1000
Output Format

N lines, each containing an integer that denotes the number of squares of maximum size, when the biscuit is cut as per the given condition.

Sample Input 

2

2 2

6 9

Sample Output 

1

6

Explanation 
	

The 1st testcase has a biscuit whose original dimensions are 2 X 2, the biscuit is uncut and is a square.

Hence the answer is 1.

The 2nd testcase has a biscuit of size 6 X 9 . We can cut it into 54 squares of size 1 X 1 , 6 of size 3 X 3 . For other sizes we will have leftovers.

Hence, the number of squares of maximum size that can be cut is 6.

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
def __gcd(a, b):
	if a == 0 or b == 0:
		return 0
	if a == b:
		return a
	if a > b:
		return __gcd(a - b, b)
	return __gcd(a, b - a)

def NumberOfSquares(x, y):
	s = __gcd(x, y)
	ans = x * y / (s * s)
	return int(ans)
n = int(input())
while n:
	n = n - 1
	(c, d) = map(int, input().split())
	print(NumberOfSquares(c, d))


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


def __gcd(a, b):
	if a == 0 or b == 0:
		return 0
	if a == b:
		return a
	if a > b:
		return __gcd(a - b, b)
	return __gcd(a, b - a)
for _ in range(int(input())):
	(x, y) = list(map(int, input().split()))
	s = __gcd(x, y)
	ans = x * y / (s * s)
	print(int(ans))


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


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


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


import math
n = int(input())
for i in range(n):
	c = list(map(int, input().split()))
	d = math.gcd(c[0], c[1])
	h = int(c[0] * c[1] / d ** 2)
	print(h)


def __gcd(a, b):
	if a == 0 or b == 0:
		return 0
	if a == b:
		return a
	if a > b:
		return __gcd(a - b, b)
	return __gcd(a, b - a)

def NumberOfSquares(x, y):
	s = __gcd(x, y)
	ans = x * y / (s * s)
	return int(ans)
t = int(input())
for i in range(t):
	(m, n) = list(map(int, input().split(' ')))
	print(NumberOfSquares(m, n))


import math
for _ in range(int(input())):
	(c, d) = list(map(int, input().split()))
	size = int(math.sqrt(c * d))
	while size > 0:
		if c * d % (size * size) == 0:
			k = c * d / (size * size)
			if c % size == 0 and d % size == 0:
				print(int(k))
				break
		size -= 1


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


t = int(input())
for i in range(t):
	(m, n) = map(int, input().split())
	mul = m * n
	while m != n:
		if m > n:
			m -= n
		else:
			n -= m
	print(mul // (m * n))