Given n, and m, find the smallest k such that -

n divides lcm (m,k) ; m divides lcm (n,k)

Even if there are no Galactic Wars, you are still a Martian. Just do it.

Input: 

First line contains a single integer T, denoting the number of Test Cases.

T lines containing space separated integers: m and n

Output:

Output T lines each containing the smallest k that satisfies the problem 

Constraints:

1 <= T <= 2000

1 <= m,n < 2^31

Time Limit: 1 second

Example:

Input:

1

3 4

Output:

12