1173 - 质数中的质数(质数筛法)
Description


如果一个质数,在质数列表中的编号也是质数,那么就称之为质数中的质数。例如:3 5分别是排第2和第3的质数,所以他们是质数中的质数。现在给出一个数N,求>=N的最小的质数中的质数是多少(可以考虑用质数筛法来做)。

Input

输入一个数N(N <= 10^6)


Output

输出>=N的最小的质数中的质数。


Examples

Input

20

Output

31
题目参数
Time Limit 1 second
Memory Limit 128 MB
提交次数 56
通过次数 20