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:
import math

t = input()
i = 0

def factors(n,list1):
    len_list = len(list1)
    list2 = []
    i = 0
    while i < len_list:
        if n%list1[i] == 0:
            j = 2
            while n%math.pow(list1[i],j) == 0:
                j += 1
            list2.append(j-1)
        else:
            list2.append(0)
        i += 1
    return list2

def prime(n):
    list1 = {}
    list2 = []
    j = 2
    while j <= n:
        list1.update({j:1})
        j += 1
    j = 2
    while j <= n:
        i = j*j
        k = 1
        while i <= n:
            list1[i] = 2
            i = j*j + k*j
            k += 1
        j += 1
    len_list = len(list1)
    i = 0
    j = 2
    while i < len_list:
        if list1[j] == 1:
            list2.append(j)
        j += 1
        i += 1
    return list2

while i != t:
    str1 = ""
    str1 = raw_input()
    n = int(str1.split()[0])
    m = int(str1.split()[1])

    if n % m  == 0:
        print int(n/m)
    else:
        list1 = []
        list2 = []
        list3 = []
        len_list = 0
        gcd = 1
        list1 = prime(min(n,m))
        list2 = factors(n,list1)
        list3 = factors(m,list1)
        len_list = len(list1)
        j = 0
        while j < len_list:
            gcd *= math.pow(list1[j],min(list2[j],list3[j]))
            j += 1
        print int((n/gcd)*(m/gcd))
    i += 1