Next Prime Finder

You are given an integer n. Your task is to compute the smallest prime number strictly greater than n. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.

Note: The solution should work efficiently even for moderately large numbers. The mathematical definition of primes is given by \(\text{if } n>1 \text{, then } n \text{ is prime if its only divisors are } 1 \text{ and } n\).

Please read input from stdin and print the answer to stdout.

inputFormat

The input consists of a single integer n (\(0 \leq n \leq 10^8\)).

outputFormat

Output a single integer representing the smallest prime number greater than n.

10

11