Hide
Problem D
Inverse Totient
Euler’s totient function $\phi (n)$ is defined as the number of integers $j$, between $1$ and $n$, such that the greatest common divisor of $j$ and $n$ equals $1$.
Given $\phi (n)$, compute the smallest possible value of $n$.
Input
The first and only line contains the value of $\phi (n)$ ($1 \le \phi (n) \le 10^{14}$).
Output
Output the smallest possible $n$ such that $\phi (n)$ is equal to the input. If there is no such $n$, output $-1$.
| Sample Input 1 | Sample Output 1 |
|---|---|
6 |
7 |
| Sample Input 2 | Sample Output 2 |
|---|---|
7 |
-1 |
| Sample Input 3 | Sample Output 3 |
|---|---|
8 |
15 |
