What Makes 2021 Special?

Interview

Time limit1sMemory limit1024 MB

Summary

Given N, find the smallest number greater than N that is the product of two consecutive primes, such as 43 × 47 = 2021.

Level: Easy2 of 10
Topics: Math, Brute force
Solved: No attempts yet

Problem

The year-end contest Good Bye 2021! on an online judge is held on December 31, 2021. Wonyi was so happy about the contest that he stared at the title, and then he noticed that 2021 is special in some way.

Yes. 2021 is the product of 43 and 47, two consecutive primes. The next year of this kind is 2491, which is 470 years later. Wonyi calls a number special when it is the product of two consecutive primes.

Write a program that finds the smallest special number greater than the given number.

Input

The first line contains the given number $N$ .

Output

Print the smallest special number greater than $N$ on the first line.

Constraints

$1 \le N \le 10\,000$
$N$ is an integer.

Hints

A prime is an integer greater than or equal to 2 that is divisible only by 1 and itself.
Primes $p$ and $q$ are consecutive when $p$ and $q$ are prime, $p < q$ , and no prime lies strictly between $p$ and $q$ .

Examples2

Example 1
Input
```
2020
```
Expected output
```
2021
```
Example 2
Input
```
2021
```
Expected output
```
2491
```