P4718 [Template] Pollard-Rho

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.

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 $T$ lines. For each test case, output the result.

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