Số đẹp là số 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² + 3² = 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, ...

Các số đẹp được đánh số thứ tự tăng dần theo giá trị:

• Số đẹp thứ nhất là 11
• Số đẹp thứ hai là 12
• ...
• Số đẹp thứ mười là 38

Yêu cầu:

Cho số nguyên dương N. Hãy tìm số đẹp thứ N.

Dữ liệu vào:

Vào từ file SODEP.INP một dòng chứa số nguyên dương N.

Kết quả:

Ghi ra file SODEP.OUT số đẹp thứ N.

Ví dụ:

SODEP.INP    |   SODEP.OUT
-------------|-------------
1            |   11
6            |   23

Ràng buộc:

• 70% số điểm tương ứng với 1 ≤ N ≤ 100
• 30% số điểm tương ứng với 10 ≤ N ≤ 10000