Small Numbers

Little Vlad has two favorite numbers $a$ and $b$. Recently at school he learned division and multiplication, and he immediately started dividing and multiplying his favorite numbers.

He wrote $a$ and $b$ in his notebook and came up with three cool operations he wants to perform on his numbers:

• Divide both numbers by one of their common divisors.
• Divide $a$ by one of its divisors $g$, multiply $b$ by $g$.
• Divide $b$ by one of its divisors $g$, multiply $a$ by $g$.

After performing an operation he erases his old numbers and replaces them with the new ones. He may continue performing operations or stop.

Since Vlad is small, he wants the numbers to be smaller. So he tries to minimize the sum of $a$ and $b$, but cannot manage it on his own. Help him determine the minimum sum he can obtain with these operations, and give an example of a final $a$ and $b$ with that sum.

Input data contains multiple test cases. The first line contains integer $t$, the number of test cases ($1 \le t \le 500$).

Each test case is described by a single line containing integers $a$ and $b$ ($1 \le a, b \le 10^9$), Vlad's favorite numbers.

For each test case output one line: a pair with the minimum sum that can be obtained by performing operations from the list.