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 + 2^2 = 5~ là 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^6~ ). Hãy tìm số đẹp thứ ~N~.

Dữ liệu: Vào từ file BEAUTY.INP Gồm nhiều tests, mỗi test cho trên một dòng chứa một số nguyên ~N~.

Kết quả: Ghi ra file BEAUTY.OUT

Mỗi test đưa ra trên một dòng là kết quả số đẹp tìm được tương ứng của mỗi test từ file dữ liệu vào.

Ví dụ: