eolymp
Competitions

Прості числа

Надпрості числа.

Сидів Андрійко на уроці, біології і нудьгував, і вирішив зайняти свій розум вправами з числами. Він згадав, що вчив на уроці математики прості числа. (Нагадаємо, що простим називається число, яке більше одиниці та має рівно два дільники, одиницю та саме число.) Виписав Андрійко прості числа за зростанням та позначив і - те в цьому порядку число pi . (число p1 = 2, p2=3, p3=5, p52=239. І тут йому спало на думку ускладнити свою задачу, і знайти такі прості числа, номери яких у списку простих чисел, що впорядковані за зростанням, є простими числами. Такі числа він назвав надпростими. Впорядкувавши всі над прості числа за зростанням, Андрій вирішив знайти таке з них, яке стоїть на k-тому місці.

Вхідні дані:

Єдиний рядок вхідних даних містить число k, 1 ≤ k ≤ 5000.

Вихідні дані:

Єдиний рядок вихідних даних повинен містити одне надпросте число, що є k-им у впорядкованій послідовності надпростих чисел.

Time limit 0.1 seconds
Memory limit 64 MiB
Input example #1
1
Output example #1
3
Input example #2
2
Output example #2
5
Input example #3
3
Output example #3
11