Nearest Prime Challenge

You are given an integer X. Your task is to find the "nearest" prime number to X based on the following conditions:

• If X is even, you must find the smallest prime number greater than X.
• If X is odd, you must find the largest prime number smaller than X.

Note that for an even X, the answer always exists as there are infinitely many primes. For an odd X, you can assume that X > 2 so that an answer always exists as well. The function to check for a prime can be implemented using any efficient method (for example, trial division up to \(\sqrt{n}\) ).

The answer should be printed to standard output.

inputFormat

The input consists of a single line containing one integer X.

For example:

12

outputFormat

Output a single integer denoting the nearest prime as per the rules:

• If X is even, output the smallest prime number greater than X.
• If X is odd, output the largest prime number smaller than X.

## sample

12

13