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 = 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, \dots~. 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~, ~\dots~, 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 vào

• Nhập từ tệp CAU2.INP một số nguyên dương duy nhất ~N~ (~1 \leq N \leq 10000~).

Kết quả ra

• Xuất ra tệp CAU2.OUT số đẹp thứ ~N~.

Ràng buộc

• Subtask ~1~ (~70 \%~): ~N \leq 10~.
• Subtask ~2~ (~30 \%~): Không có ràng buộc gì thêm.

Ví dụ 1

Dữ liệu vào

1

Kết quả ra

11

Ví dụ 2

Dữ liệu vào

6

Kết quả ra

23