메시지

면접 대비

시간 제한2초메모리 제한1024 MB

요약

정수 k가 주어질 때 2p + 1도 소수가 되는 소수 p 중 k번째로 작은 값을 구합니다.

난이도: 쉬움10점 중 3점
유형: 정수론, 구현
정답자: 아직 제출이 없습니다

문제

페탸와 바샤는 스파이 놀이를 계속하고 있다. 이번에는 페탸가 바샤에게 암호화된 메시지를 보냈다. 이를 복호화하는 키는 두 소수 $p$ 와 $q$ 이다. 페탸는 이 두 수가 $q = 2p + 1$ 관계를 만족한다고 알려 주었다. 또 $p$ 는 이 관계를 만족하는 소수 $q$ 가 존재하는 소수 중 작은 순서로 $k$ 번째인 수이다.

바샤가 메시지를 읽을 수 있도록 그러한 $p$ 를 찾아라.

입력

입력 파일의 유일한 줄에 정수 $k$ ( $1 \le k \le 30000$ )가 주어진다. 이는 $p$ 의 순번이다.

출력

출력 파일에 $p$ 를 나타내는 정수 하나를 출력한다.

예제2

예제 1
입력
```
1
```
예상 출력
```
2
```
예제 2
입력
```
4
```
예상 출력
```
11
```