Least Common Multiple

Time limit

Memory limit

128 MB

Problem

For two natural numbers A and B, a common multiple is a natural number that is a multiple of both A and B. The least common multiple is the smallest such number.

Given several pairs of natural numbers A and B, write a program that computes the least common multiple for each pair.

Input

The first line contains the number of test cases T (1 ≤ T ≤ 1,000). Each of the next T lines contains two natural numbers A and B (1 ≤ A, B ≤ 45,000).

Output

For each test case, print the least common multiple of A and B on its own line, in the same order as the input.