← 返回题目列表

AtCoder · abc284_d

G. 2023 年新年快乐

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

给你一个正整数 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.

输入

输入由标准输入按以下格式给出,其中 \text{test}_i 代表 i-第一个测试用例:

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

每个测试用例均采用以下格式:

N

输出

打印 T 行。

的 i-th (1\leq i \leq T) 行应包含 p 和 q 为 i- 第一个测试用例,以空格分隔。 在该问题的约束下,可以证明素数对 p 和 q 这样 N=p^2q 是独一无二的。


样本输入 1

3
2023
63
1059872604593911

示例输出 1

17 7
3 7
104149 97711

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