#P3667. Rabin-Miller算法
Rabin-Miller算法
## 题目描述
给定若干整数。对每个整数判断它是否为质数。如果它是合数,求出它的最大质因子。
## 输入格式
第一行一个整数 $T$,表示测试组数。接下来 $T$ 行,每行一个整数 $n$。
## 输出格式
每组输出一行。若 $n$ 是质数,输出 `Prime`,否则输出它的最大质因子。
## 数据范围
$1\le T\le350$。本站评测保证 $2\le n\le2^{63}-1$。
```input1
6
2
13
134
8897
1234567654321
1000000000000
```
```output1
Prime
Prime
67
41
4649
5
```