题目描述

小珅是个天才，它能够背下来1000000以内所有的质数，猴博士为了检验这个事情的真假现准备任意说出一个数n，让小珅背出第n个质数是多少？你能编写一个程序输出第n个质数，来检验小珅小珅回答的正确与否吗？

输入格式

输入共1行：

一个正整数n，表示后博士抽背的是第n个质数。

输出格式

输出共1行：

一个正整数，表示在范围内的第n个质数的值。

输入样例 #1

6

输出样例 #1

13

输入样例 #2

26

输出样例 #2

101

输入样例 #3

500

输出样例 #3

3571

数据范围与约定

1≤n≤70000；1000000以内共78498个质数。