Problem: 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 some parts of his plots. The specialty of his plot 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 plot into minimum possible square plots so that he can get maximum profit out of this.
So your task is to find the minimum number of square plots that can be formed out of the rectangular plot.

Input

The input consists of T number of test cases. T lines follow. Each line consists of two integers N and M which denotes the length and breadth of the rectangle.


Output
Output is a single line which denotes the minimum number of square plots that can be formed

Constraints

1<=T<=20 
1<=M<=10000 
1<=N<=10000 

Input:
2
10 15
4 6

Output:
6
6

Solution (in PYTHON):

Solution:
## Codechef
## Farmer and his plot
## 2016.03.03. Thu

## the function that finds larger number
def largenum(m,n):
    if m> n:
        return m
    else:
        return n

## the function that finds smaller number
def smallnum(m,n):
    if m<n:
        return m
    else:
        return n
    
## the function that can find the greatest common divisor of two numbers
def GCD(m,n):
    large = largenum(m,n)
    small = smallnum(m,n)
    if large % small == 0:
        return small
    else:
        return GCD(large-small, small)


testCases = int(raw_input())

for i in xrange(testCases):
    inputArr = map(int, raw_input().strip().split())
    length = inputArr[0]
    breadth = inputArr[1]
    gcd = GCD(length, breadth)
    tnw = length / gcd ## the number of width of squares
    tnh = breadth / gcd ## the number of height of squres
    output = tnw * tnh
    print output