THỰC HÀNH

Một số đượ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ố. Ví dụ, 12 là một số đẹp vì 1²+2² = 5 – số nguyên tố.

Các số đẹp được đánh số theo thứ tự tăng dần của giá trị, bắt đầu từ 1 trở đi.

Yêu cầu: Cho số nguyên n (1 ≤ n ≤ 10 000). Hãy tìm số đẹp thứ n.

Input:

Gồm nhiều tests, mỗi test cho trên một dòng chứa một số nguyên n.

Output:

Kết quả mỗi test đưa ra trên một dòng.

Ví dụ:

Input:
1
2
6
Output:
11
12
23