Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Nearest Co-Prime

By TarifEzaz · Limits 1s, 512 MB

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

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

Input

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

Output

In one line, print the desired result.

Sample

InputOutput
1
2

    Discussion

    Statistics


    95% Solution Ratio

    mahade31Earliest, 3M ago

    chandlerFastest, 0.0s

    nfs277Lightest, 0 B

    imamanik05Shortest, 21B

    Submit

    Login to submit

    Editorial

    If an integer NNN is divisible by xxx, then N+xN + xN+x is also divisible by xxx. If we want to find...

    Related Contests