問題文

正整数 $N$ が与えられます。$N$ は、$2$ つの相異なる素数 $p,q$ を用いて $N=p^2q$ と表せることがわかっています。

$p,q$ を求めてください。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

• 入力は全て整数
• $1\\leq T\\leq 10$
• $1\\leq N \\leq 9\\times 10^{18}$
• $N$ は、$2$ つの相異なる素数 $p,q$ を用いて $N=p^2q$ と表せる

入力

入力は以下の形式で標準入力から与えられる。ここで $\\text{test}_i$ は $i$ 番目のテストケースを意味する。

$T$ $\\text{test}_1$ $\\text{test}_2$ $\\vdots$ $\\text{test}_T$

各テストケースは以下の形式で与えられる。

$N$

出力

$T$ 行出力せよ。

$i\\ (1\\leq i \\leq T)$ 行目には、$i$ 番目のテストケースにおける $p,q$ を空白区切りで出力せよ。 なお、この問題の制約下では、$N=p^2q$ を満たす素数 $p,q$ の組は $1$ 通りしか存在しないことが証明できる。

入力例 1

3
2023
63
1059872604593911

出力例 1

17 7
3 7
104149 97711

$1$ 番目のテストケースについて、$N=2023=17^2\\times 7$ です。よって、$p=17,q=7$ です。