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


94% Solution Ratio

mahade31Earliest, Apr '21

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

Toph uses cookies. By continuing you agree to our Cookie Policy.