Next Prime Number

Given a non-negative integer n, your task is to find the smallest prime number that is strictly greater than n. Recall that a prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. Formally, a number \(p\) is prime if \(p > 1\) and for every integer \(d\) such that \(1 < d < p\), \(d\) does not divide \(p\). For example, if n is 7, the next prime is 11; if n is 23, the answer is 29.

inputFormat

The input is provided via stdin and consists of a single integer n (0 ≤ n ≤ 10⁶).

outputFormat

Output to stdout the smallest prime number that is strictly greater than n.

7

11