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

Please log in to submit a solution to this problem

Log in