Problem Description

The Miller Rabin algorithm is an efficient method for primality testing. Although it is a probabilistic primality test, when multiple bases are chosen, the accuracy is acceptable.

Pollard rho is a rather “mystical” method used to find a non-trivial factor of a composite number $n$ in expected time complexity $O(n^{1/4})$. In fact, Introduction to Algorithms gives $O(\sqrt p)$, where $p$ is the smallest factor of $n$, and $p$ is coprime with $n/p$. However, these are all expected results and may not match reality. In practice, the Pollard rho algorithm runs quite well.

Here you need to write a program: for each number, check whether it is prime. If it is prime, output Prime; otherwise, output its largest prime factor.

Input Format

The first line contains $T$, the number of test cases (not greater than $350$).

The next $T$ lines each contain an integer $n$, where $2 \le n \le {10}^{18}$ is guaranteed.

Output Format

Output $T$ lines.

For each test case, output the result.

6
2
13
134
8897
1234567654321
1000000000000

Prime
Prime
67
41
4649
5

Hint

On 2018.8.14, two new groups of testdata were added, and the time limit was increased to 2 s. Thanks to @whzzt.

On 2022.12.22, new testdata were added. Thanks to @ftt2333 and Library Checker.

by @will7101.

Translated by ChatGPT 5