1173 - 质数中的质数(质数筛法)
描述


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

输入

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


输出

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


样例

输入

20

输出

31
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 56
通过次数 20