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: interview

Starter code:

Solutions:
def __gcd(a, b): 
  
 # Everything divides 0  
 if (a == 0 or b == 0): 
  return 0; 
 
 # base case 
 if (a == b): 
  return a; 
 
 # a is greater 
 if (a > b): 
  return __gcd(a - b, b); 
 return __gcd(a, b - a); 
 
# Function to find  
# number of squares 
def NumberOfSquares(x, y): 
  
 # Here in built PHP 
 # gcd function is used 
 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))

# cook your dish here
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)

# cook your dish here
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)




# Python3 code for calculating
# the number of squares

# Recursive function to
# return gcd of a and b
def __gcd(a, b):
 # Everything divides 0
 if (a == 0 or b == 0):
  return 0;

  # base case
 if (a == b):
  return a;

  # a is greater
 if (a > b):
  return __gcd(a - b, b);
 return __gcd(a, b - a);


# Function to find
# number of squares
def NumberOfSquares(x, y):
 # Here in built PHP
 # gcd function is used
 s = __gcd(x, y);

 ans = (x * y) / (s * s);

 return int(ans);


# Driver Code

t = int(input())
for i in range(t):
 m,n = list(map(int,input().split(' ')))
# Call the function
# NumberOfSquares
 print((NumberOfSquares(m, n)));

# This code is contributed
# by mit


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))