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~.

Input

• Chứa duy nhất một số nguyên ~N~ (~1 ≤ N ≤ 10000~).

Output

• Số đẹp thứ ~N~.

Scoring

• Subtask 1 (70%): ~N ≤ 10~;

• Subtask 2 (30%): Không ràng buộc gì thêm.

Examples

Input

1

Output

11

Input

6

Output

23