505002 - Pollard-Rho

【题目描述】Pollard-Rho(PollardRho)

对于给定的每个数字检验是否是质数,是质数就输出 Prime;如果不是质数,输出它最大的质因子是哪个。

输入

第一行一个整数T代表数据组数(T<351)。 以下T 行,每行一个整数n(2≤n≤10^18)。

输出

输出T行答案。

样例

输入

6
2
13
134
8897
1234567654321
1000000000000

输出

Prime
Prime
67
41
4649
5
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题