新年快乐 2023

题目描述

给定一个正整数 $N$。已知 $N$ 可以表示为 $N=p^2q$,其中 $p$ 和 $q$ 是两个不同的质数。

求 $p$ 和 $q$。

需要解决 $T$ 组测试数据。

输入格式

输入按以下格式从标准输入给出,其中 $\text{test}_i$ 表示第 $i$ 组测试数据:

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

每组测试数据按以下格式给出:

$N$

输出格式

输出 $T$ 行。

第 $i$ 行 $(1 \le i \le T)$ 输出第 $i$ 组测试数据的 $p$ 和 $q$,用空格分隔。

在本题约束下,可以证明满足 $N=p^2q$ 的质数对 $(p, q)$ 是唯一的。

样例

3
2023
63
1059872604593911

17 7
3 7
104149 97711

对于第一组测试数据,有 $N=2023=17^2 \times 7$,因此 $p=17$,$q=7$。

数据范围

• 输入中的所有值都是整数。
• $1 \le T \le 10$
• $1 \le N \le 9 \times 10^{18}$
• $N$ 可以表示为 $N=p^2q$,其中 $p$ 和 $q$ 是两个不同的质数。