Nearest Prime

Given an integer n, find the nearest prime number to n. If n is already a prime, then output n itself. If there are two prime numbers equally distant from n, choose the smaller one.

For example:

• If n = 10, the nearest prime is 11.
• If n = 14, the nearest prime is 13.
• If n = 30, the nearest prime is 29.

The solution involves checking for prime numbers using the classic trial division method. A helpful hint is that a number n is prime if it is not divisible by any number less than or equal to \(\sqrt{n}\) (with appropriate exceptions for small numbers).

inputFormat

The input is provided via standard input. It consists of a single integer n (where \(1 \leq n \leq 10^8\)).

outputFormat

Output the nearest prime number to n to standard output. If there are two candidates equally close to n, output the smaller one.

## sample

10

11

</p>