A. Ginger's number
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Ginger have two positive integers $$$x, y$$$, you have to do exactly one operation:

Choose two positive integers $$$a, b$$$, change $$$x$$$ to $$$\dfrac{x}{a}$$$, and change $$$y$$$ to $$$\dfrac{y}{b}$$$, ($$$a$$$ must be a divisor of $$$x$$$, $$$b$$$ must be a divisor of $$$y$$$ and $$$\gcd(\dfrac{x}{a}, \dfrac{y}{b}) = 1$$$).

Find the minimum value of $$$a \times b$$$.

Input

The first line of input contains a single integer $$$T$$$ $$$(1 \le T \le 10 ^ 5)$$$ — the number of input test cases.

For each test case, the only line of input contains two positive integers $$$x, y$$$ $$$(1 \le x,y \le 10 ^ 9)$$$.

Output

Print the minimum value of $$$a \times b$$$.

Example
Input
1
114514 1919810
Output
2