Given two positive integers a and b, compute their least common multiple (LCM). The LCM of a and b is the smallest positive integer that can be divided by a and b with no reminder.
First line contains a positive integer t (t<=1000), which indicates the number of test cases in the input. In the next t line, each line contains two positive integers a, b, which are smaller or equal to 106.
For each case, output the LCM of a and b in a line.