Description

In Minecraft, there are three dimensions in the simple world, one of which is known as “The End”. In this dimension, the Ender Dragon is usually symbolized as the final boss of Minecraft.

Now we, you, and Steve want to beat the dragon. However, we find that the dragon is telling a puzzle. We must solve it before fighting against the dragon. Please stand by our side to fight against the dragon. The puzzle goes as follows.

Given two positive integers $x$ and $y$, please find two integers $a$ and $b$, such that

$$\sqrt{\dfrac{\operatorname{lcm}(x,y)}{\gcd(x,y)}}=a\sqrt{b}$$

and to maximize $a \cdot b$.

Here, $\gcd(a, b)$ represents the greatest common divisor of $a, b$, while $\operatorname{lcm}(a, b)$ represents the least common multiple of $a, b$.

Input Format

The first line contains an integer $T (1 \leq T \leq 10^4)$ indicating the number of test cases.

Of the following $T$ lines, each contains two integers $x$ and $y (1 \leq x, y \leq 10^9)$, representing the puzzle.

Output Format

Output $T$ lines. Each contains two integers $a$ and $b$, indicating the answer to each test case.

2
1 1
4 4

1 1
1 1

Hint

Dear all participants:

This problem may be the very first page, but not where the story line ends. Please believe in yourself all the time, wishing you with my singing, “Long live all the mountains we moved, I had the time of my life fighting dragons with you”.