Số đẹp

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 + 2^2 = 5 và 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≤n≤100000). Hãy tìm số đẹp thứ n.

Dữ liệu: Vào từ file văn bản BEAUTY.INP gồm nhiều dòng, mỗi dòng là một bộ kiểm thử chứa một số nguyên dương n.

Kết quả: Ghi ra file văn bản BEAUTY.OUT ghi kết quả của mỗi bộ kiểm thử, mỗi bộ được ghi trên một dòng.

Ví dụ:

BEAUTY.INP

1

BEAUTY.OUT

11

BEAUTY.INP

6

BEAUTY.OUT

23