102843: [AtCoder]ABC284 D - Happy New Year 2023

Problem Statement

You are given a positive integer $N$. It is known that $N$ can be represented as $N=p^2q$ using two different prime numbers $p$ and $q$.

Find $p$ and $q$.

You have $T$ test cases to solve.

Constraints

• All values in the input are integers.
• $1\leq T\leq 10$
• $1\leq N \leq 9\times 10^{18}$
• $N$ can be represented as $N=p^2q$ using two different prime numbers $p$ and $q$.

Input

The input is given from Standard Input in the following format, where $\text{test}_i$ represents the $i$-th test case:

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

Each test case is in the following format:

$N$

Output

Print $T$ lines.

The $i$-th $(1\leq i \leq T)$ line should contain $p$ and $q$ for the $i$-th test case, separated by a space. Under the constraints of this problem, it can be proved that the pair of prime numbers $p$ and $q$ such that $N=p^2q$ is unique.

Sample Input 1

3
2023
63
1059872604593911

Sample Output 1

17 7
3 7
104149 97711

For the first test case, we have $N=2023=17^2\times 7$. Thus, $p=17$ and $q=7$.

问题描述

给你一个正整数$N$。已知$N$可以用两个不同的质数$p$和$q$表示为$N=p^2q$。

找出$p$和$q$。

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

约束

• 输入中的所有值都是整数。
• $1\leq T\leq 10$
• $1\leq N \leq 9\times 10^{18}$
• $N$可以用两个不同的质数$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

样例输出1

17 7
3 7
104149 97711

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