Một số nguyên dương được gọi là đặc biệt nếu tổng bình phương các chữ số (ở dạng thập phân) của nó là một số nguyên tố. Ví dụ: 12 là số đặc biệt vì 1^2 + 2^2 = 5 là số nguyên tố.

Yêu cầu: Cho số nguyên dương n. Hãy tìm số đặc biệt nhỏ nhất lớn hơn n.

Input

Một dòng ghi số nguyên dương n (1 ≤ n ≤ 10⁹).

Output

Một dòng ghi số đặc biệt nhỏ nhất lớn hơn n.

Ví dụ — Input

11

Ví dụ — Output

12

Giải thích: 1^2 + 2^2 = 5 là số nguyên tố.