First Prime Not Smaller Than n

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Find the smallest prime $p\ge n$. A prime is an integer greater than 1 with exactly two positive divisors. Return $n$ itself if prime; for $n=1$, return 2. A trial-division solution needs no array.

Input

One integer $1\le n\le10^6$.

Output

Print the smallest prime not smaller than $n$.

Subtasks

• Subtask 1 (20%): $1\le n\le 30$.

• Subtask 2 (30%): $1\le n\le 10000$.

• Subtask 3 (50%): $1\le n\le 1000000$.

Examples

Example 1

Input:

14

Output:

17

Explanation:

Check candidates beginning at 14; the first prime is 17.

Example 2

Input:

1

Output:

2

Explanation:

Check candidates beginning at 2; the first prime is 2.