Message

Interview

Time limit2sMemory limit1024 MB

Summary

Given k, find the k-th smallest prime p such that 2p + 1 is also prime.

Level: Easy3 of 10
Topics: Number theory, Implementation
Solved: No attempts yet

Problem

Petya and Vasya keep playing spies. This time Petya sent Vasya an encoded message. The two keys for decoding it are prime numbers $p$ and $q$ . Petya told Vasya that these numbers satisfy $q = 2p + 1$ , and that $p$ is the $k$ -th smallest prime for which such a prime $q$ exists.

Help Vasya read the message by finding this $p$ .

Input

The only line of the input file contains an integer $k$ ( $1 \le k \le 30000$ ), the ordinal number of $p$ .

Output

Print the single number $p$ to the output file.

Examples2

Example 1
Input
```
1
```
Expected output
```
2
```
Example 2
Input
```
4
```
Expected output
```
11
```