/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
正整数 N が与えられます。N は、2 つの相異なる素数 p,q を用いて N=p^2q と表せることがわかっています。
p,q を求めてください。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 入力は全て整数
- 1\leq T\leq 10
- 1\leq N \leq 9\times 10^{18}
- N は、2 つの相異なる素数 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 通りしか存在しないことが証明できる。
入力例 1
3 2023 63 1059872604593911
出力例 1
17 7 3 7 104149 97711
1 番目のテストケースについて、N=2023=17^2\times 7 です。よって、p=17,q=7 です。
Score : 400 points
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.