#ABC284D. 2023 新年快乐

2023 新年快乐

AT_abc284_d [ABC284D] Happy New Year 2023

题目描述

\hspace{15pt}给定一个正整数 nn。已知 nn 可以表示为 n=p2qn=p^2 q,其中 pp 和 qq 是两个不同的素数。

\hspace{15pt}请你求出 pp 和 qq。

\hspace{15pt}本题有 tt 组测试数据,请分别输出每组的答案。

输入格式

\hspace{15pt}每个测试文件均包含多组测试数据。第一行输入一个整数 t(1≦t≦10)t \left(1 \leqq t \leqq 10 \right) 代表数据组数,每组测试数据描述如下:

\hspace{15pt}每组测试数据输入一行,包含一个整数 n(1≦n≦9×1018)n \left(1 \leqq n \leqq 9 \times 10^{18} \right),代表该组测试数据给定的正整数。保证 nn 可以表示为 n=p2qn=p^2 q,其中 pp 和 qq 是两个不同的素数。

输出格式

\hspace{15pt}对于每一组测试数据,新起一行,输出两个整数 p,qp,q,两者之间用一个空格隔开。

\hspace{15pt}根据本题的限制条件,可以证明满足 n=p2qn=p^2 q 的素数 pp 和 qq 的组合只有唯一一组。

测试样例

3
2023
63
1059872604593911
17 7
3 7
104149 97711

样例 1 解释

\hspace{15pt}对于第 11 组测试数据,n=2023=172×7n=2023=17^2 \times 7,因此 p=17,q=7p=17,q=7。