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

Starter code:

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


# cook your dish here

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


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



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


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

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)

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

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

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

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)


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)
 
  


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

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


# cook your dish here
a= int(input())
for i in range(a):
 rect= input()
 rect= rect.split(" ")
 b= int(rect[0])
 l= int(rect[1])
 # print(b,l)
 maxx=1
 
 for i in range(1,b+1):
  if(b%i==0 and l%i==0):
   maxx=i

 print(l//maxx * b//maxx)
  
 


# cook your dish here
a= int(input())
for i in range(a):
 rect= input()
 rect= rect.split(" ")
 b= int(rect[0])
 l= int(rect[1])
 # print(b,l)
 maxx=1
 
 for i in range(1,b+1):
  if(b%i==0 and l%i==0):
   maxx=i

 print(l//maxx * b//maxx)
  
 


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