Số đẹp

Số đẹp là số nguyên dương có tổng bình phương các chữ số của nó (trong dạng biểu diễn thập phân) là một số nguyên tố.

Ví dụ: \(23\) là một số đẹp vì \(2^2 + 3^2 = 13\) là một số nguyên tố.

Dãy các số đẹp lần lượt là: \(11, 12, 14, 16, 21, 23, 25, 27, 32, 38, \dots\)

Các số đẹp được đánh số thứ tự tăng dần theo giá trị, bắt đầu từ số thứ nhất là \(11\), số thứ hai là \(12\), \(\dots\), số thứ mười là \(38\), \(\dots\)

Yêu cầu. Cho số nguyên dương \(N\). Hãy tìm số đẹp thứ \(N\).

Input

Một dòng chứa số nguyên dương \(N\) (\(N \le 10^4\)).

Output

Ghi ra số đẹp thứ \(N\).

Scoring

• (\(70\%\)) \(1 \le N \le 10\);

• (\(30\%\)) \(10 < N \le 10^4\).