#627 BCD Operation

Statement

Statement language

For two positive integers $a,b$ , define the BCD operation as follows.

\operatorname{bcd}(a,b)=\gcd(a,b)\times\operatorname{lcm}(a,b)

Here, $\gcd(a,b)$ is the greatest common divisor of $a$ and $b$ , and $\operatorname{lcm}(a,b)$ is their least common multiple.

The greatest common divisor is the largest positive integer that divides both numbers without a remainder.
The least common multiple is the smallest positive integer that is a multiple of both numbers.

For example, $6$ and $8$ have greatest common divisor $2$ and least common multiple $24$ , so $\operatorname{bcd}(6,8)=2\times24=48$ .

Given two positive integers $A,B$ , find $\operatorname{bcd}(A,B)$ .

Input

The input has the following format.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

Output

For each test case, print $\operatorname{bcd}(A,B)$ on its own line.

Constraints

$1\leq T\leq100\,000$ .
$1\leq A,B\leq1000$ in every test case.
All input values are integers.

Subtasks

#	Score	Constraints
1	17	$A\leq10$ , $B\leq10$ .
2	83	No additional constraints.

Samples

Input

Output

48
7
1000000

In the first test case, the greatest common divisor is $2$ and the least common multiple is $24$ , giving $48$ . In the second, they are $1$ and $7$ , giving $7$ . In the third, both are , giving .