Concatenated Numbers#8706

Concatenated Numbers

1 second
64 megabytes
Hard

Kostya had been studying a sequence of prime numbers listed on the endpaper of an algebra book (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61…) for several days. He then came up with the idea to expand this sequence by including numbers formed by "gluing" two prime numbers together. As a result, numbers like 25, 112, 292, and many others were added to this sequence. Now, the sequence of prime and "glued" numbers appears as follows: 2, 3, 5, 7, 11, 13, 17, 19, 22, 23, 25, 27, 29, 31, 32, 33, 35, 37, 41, 43, 47, 52, 53, 55, 57, 59, 61…. Kostya now faces the challenge of identifying which number is at a specific position in this newly formed sequence. Help Kostya find the number at position in this sequence.

Input

A single integer (1 \le N \le 500000).

Output

A single integer , which is located at the -th position in this sequence.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading