Concatenated Numbers
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 N in this sequence.
Input
A single integer N (1 ≤ N ≤ 500000).
Output
A single integer K, which is located at the N-th position in this sequence.