Một số nguyên dương đượ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ố. Chẳng hạn: Số 12 là số đẹp vì \(1^2 + 2^2 = 5\) là số nguyên tố.

Các số đẹp được sắp xếp theo thứ tự tăng dần của giá trị bắt đầu từ 1.

Yêu cầu

Cho số nguyên dương \(n (1 \leq n \leq 10000)\). Hãy tìm số đẹp thứ \(n\).

Dữ liệu

Chỉ một dòng chứa một số nguyên dương n.

Kết quả

Ghi ra kết quả tìm được.

INPUT

6

OUTPUT

23