Problem D
Logri
Languages
en
is
You and your friend communicate only by letters. But you are growing tired of how old-school this process is. To modernize your communications you want to use cryptography to encrypt your letters.
A part in this encryption process is the exchange of cryptographic keys. You intend to use the Diffie-Hellman key change method. This method is based on difficulty of solving
\begin{equation*} a^ x = b \mod m \end{equation*}for $x$. A solution to this equation is called a discrete logarithm of $b$ with base $a$ and with respect to $m$. For this computation to be difficult $m - 1$ must have a large prime factor. We say that the security score of $m$ is the largest prime factor of $m - 1$.
Your friend has provided you with a list of numbers and you want to find the security score of these numbers, to know which is the safest.
Input
The only line of the input contains a single integer $m$ ($1 \leq m \leq 10^{18}$).
Output
The output should contain a single integer, the security score of $m$.
| Sample Input 1 | Sample Output 1 |
|---|---|
23 |
11 |
| Sample Input 2 | Sample Output 2 |
|---|---|
32 |
31 |
| Sample Input 3 | Sample Output 3 |
|---|---|
999999866000004474 |
999999937 |
| Sample Input 4 | Sample Output 4 |
|---|---|
576460752303423489 |
2 |
