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ì 12 + 22 = 5 là số nguyên tố.
Các số đẹp được sắp xếp theo thứ tự tăng dần của giá trị bắt đầu từ 1.
Yêu cầu: Cho số nguyên dương n (1 <= n <= 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.
Kết quả:
- Ghi ra kết quả tìm được.
Input
6
Output
23
Nguồn: Bài 2 TS10 LQĐ TPĐN '2014