Số đẹp là số có tổng bình phương các chữ số của nó là một số nguyên tố.

Ví dụ số 23 là số đẹp vì \(2^2+3^2=13\), \(13\) là 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ị, bắt đầu từ số thứ nhất là 1, số thứ 2 là số 2, …

Yêu cầu: Cho số nguyên dương \(N\). Tìm số đẹp thứ \(N\).

Dữ liệu vào từ tệp văn bản SODEP7.INP có cấu trúc:

• Gồm một dòng chứa số nguyên \(N (1≤N≤10^4 ).\)

Kết quả ghi vào tệp SODEP7.OUT có cấu trúc:

• Ghi một số nguyên là số đẹp thứ \(N\) tìm được.

Ràng buộc

• Subtask 1: có 70% số test với \(N≤10^2.\)

• Subtask 2: có 30% số test với \(N≤10^4.\)

Sample Input

1

Sample Output

11