Two numbers are relatively prime or co-prime if their greatest common divisor is $1$.

In this problem, you will be given an integer $\textbf{N}$, you will have to find out the the smallest number $\textbf{x ( x > N )}$, so that $\textbf{x}$ and $\textbf{N}$ are relatively prime.

Input

The only line will have one input $N$ $( 1 \leq N \leq 10^{18} )$

Output

In one line, print the desired result.

Sample

Input	Output
1	2