Smallest Prime Factor with Maximum Frequency

Given a positive integer (N), perform its prime factorization and determine the frequency of each prime factor. Your task is to find the smallest prime factor (p_{min}) such that its frequency (f(p_{min})) is strictly greater than the frequency of every other prime factor in the factorization. In other words, if (f(p_{min}) > f(q)) for every other prime (q) in the decomposition, then output (p_{min}). If (N) has only one prime factor, output that factor. If no such prime factor exists, output -1.

For example:

• For \(N=20\): The prime factors are \(2^2\) and \(5^1\). Since \(2\) (the smallest prime) has frequency 2 which is greater than frequency 1 of \(5\), the answer is 2.
• For \(N=45\): The prime factors are \(3^2\) and \(5^1\). The smallest prime among these is 3 and its frequency (2) is greater than that of 5. Thus the answer is 3.
• For \(N=18\): The prime factors are \(2^1\) and \(3^2\). Even though 3 appears more often, it is not the smallest prime factor, so the answer is -1.
• For \(N=15\): The prime factors are \(3^1\) and \(5^1\). The frequencies are equal so the answer is -1.

Note: All input is read from standard input (stdin) and output is written to standard output (stdout).

inputFormat

The input consists of a single line containing a positive integer (N) ((2 \leq N \leq 10^{12}) for practical purposes).

outputFormat

Output a single integer which is the smallest prime factor satisfying the condition, or -1 if no such prime factor exists.## sample

20

2