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^2 + 3^2~ 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ị bắt đầu số thứ nhất là ~11~, số thứ hai là ~12~, ..., số 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 đầu vào

Gồm duy nhất một số nguyên ~N~ ~(1 \le N \le 10000)~.

Dữ liệu đầu ra

Gồm duy nhất một số là số đẹp thứ ~N~.

Ràng buộc dữ liệu

• Có 70% test ứng với 70% số điểm có ~n \le 10~;
• Có 30% test ứng với 30% số điểm không có ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

1

OUTPUT

11

Ví dụ 2

INPUT

6

OUTPUT

23