配点 : $400$ 点

問題文

正整数 $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$ 通りしか存在しないことが証明できる。

3
2023
63
1059872604593911

17 7
3 7
104149 97711

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