This is a number theory problem
题号：NC237152
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

PaiGuDragon is an excellent number theory player.

For a positive interger number x, if the digit sum of x is a prime number, the PaiGuDragon calls x nice number.(i.e. digit sum of 269 equals to 17, and 17 is a prime number so 269 is nice!)

PaiGuDragon is curious about what is the n th smallest nice number.

输入描述:

An interger

输出描述:

Output the n th smallest nice number.
示例1

输入

复制 
3

输出

复制 
5
示例2

输入

复制 
5

输出

复制 
11
示例3

输入

复制 
12

输出

复制 
25
示例4

输入

复制 
100

输出

复制 
269