题目描述

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

找出 $p$ 和 $q$。

你需要解决 $T$ 个测试用例。

约束条件

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

输入

输入的格式如下所示：

$T$

$test_1$

$test_2$

$\vdots$

$test_T$

每个测试用例的格式如下所示：

$N$

输出

打印 $T$ 行。

第 $i$ 行（$1 \leq i \leq T$）应包含第 $i$ 个测试用例的 $p$ 和 $q$，用一个空格分隔。根据此问题的约束条件，可以证明使得 $N=p^2q$ 成立的质数对 $p$ 和 $q$ 是唯一的。

示例输入1

3
2023
63
1059872604593911

示例输出1

17 7
3 7
104149 97711

对于第一个测试用例，我们有 $N=2023=17^2 \times 7$。因此，$p=17$ 而 $q=7$。