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³¹

Example

Input:
1
3 4
Output:
12