Một số nguyên dương được gọi là số đẹ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ố.

Ví dụ. 12 là số đẹp vì 1² + 2² = 5 là số nguyên tố.

Trong dãy số đẹp được đánh số 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 \leq n \leq 100000)\). Hãy tìm số đẹp thứ \(n\).

Dữ liệu vào: Gồm nhiều dòng, mỗi dòng chứa một số nguyên dương \(n\).

Kết quả: Ghi kết quả của mỗi dòng trong dữ liệu vào, mỗi kết quả ghi trên 1 dòng.

Ví dụ: