Prime or Largest Prime Factor

This problem requires you to determine for each given number whether it is a prime number or not. If the number is a prime, output Prime (without quotes). Otherwise, compute and output the largest prime factor of the number.

You are encouraged to use the Miller–Rabin algorithm for fast probabilistic prime checking. Although Miller–Rabin is a probabilistic test, when multiple bases are used, the probability of error is negligible.

For composite numbers, you may use the Pollard Rho algorithm to obtain a nontrivial factor. In theory, the expected run time of Pollard Rho is \(O(n^{1/4})\), or \(O(\sqrt{p})\), where \(p\) is the smallest prime factor of \(n\) (with \(p\) and \(n/p\) coprime). In practice, the algorithm runs quite efficiently.

Note: For the purpose of this problem, if the input number is 1, simply output 1.

inputFormat

The input begins with an integer \(T\) (\(1 \leq T \leq 10^5\)) representing the number of test cases. Each of the following \(T\) lines contains a single integer \(n\) (\(1 \leq n \leq 10^{18}\)).

outputFormat

For each test case, output a single line:

• If \(n\) is prime, output Prime.
• If \(n\) is composite, output its largest prime factor.

sample

4
3
12
1
100

Prime
3
1
5