题目描述

Miller Rabin 算法是一种高效的质数判断方法。虽然是一种不确定的质数判断法，但是在选择多种底数的情况下，正确率是可以接受的。

Pollard Rho是一个非常玄学的方式，用于在$O(n^{1/4})$的期望时间复杂度内计算合数n的某个非平凡因子。事实上算法导论给出的是$O(\sqrt p)$，$p$是$n$的某个最小因子，满足$p$与$n/p$互质。但是这些都是期望，未必符合实际。但事实上Pollard Rho算法在实际环境中运行的相当不错。

这里我们要写一个程序，对于每个数字检验是否是质数，是质数就输出Prime；如果不是质数，输出它最大的质因子是哪个。

输入格式

第一行，$T$代表数据组数（不大于$350$）

以下$T$行，每行一个整数$n$，保证$1 < n\le 10^{18}$。

输出格式

输出$T$行。

对于每组测试数据输出结果。

6
2
13
134
8897
1234567654321
1000000000000

Prime
Prime
67
41
4649
5

提示

2018.8.14 新加数据两组，时限加大到2s，感谢 @whzzt

by @will7101