Đề bài

Một số nguyên dương được gọi là đẹp nếu 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ố. Chẳng hạn, số 12 là số đẹp vì \(1^2 + 2^2 = 5\) là một số nguyên tố.

Các số đẹp được sắp xếp theo thứ tự tăng dần bắt đầu từ 1.

Yêu cầu: Cho một số nguyên dương \(n\) (\(1 \leq n \leq 10000\)), hãy tìm số đẹp thứ \(n\).

Dữ liệu vào

Chỉ một dòng chứa một số nguyên dương \(n\).

Dữ liệu ra

Ghi ra số đẹp thứ \(n\) tìm được.

Giới hạn

\(1 \leq n \leq 10000\)

Sample Input

6

Sample Output

23

Giải thích

10 số đẹp đầu tiên theo thứ tự tăng dần là: \(11, 12, 14, 16, 21, 23, 25, 27, 32, 38\).

Sample Input 2

10000

Sample Output 2

50695