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

Example

Input:
1
3 4
Output:
12