Tìm số nguyên tố

Bình vừa được học về số nguyên tố và rất thích bài học này. Như bạn đã biết, số nguyên tố là số nguyên dương lớn hơn $1$, chỉ có hai ước là $1$ và chính nó. Bình miệt mài ghép các số nguyên tố bắt đầu từ $2$, theo thứ tự tăng dần (viết liền các số $2,3,5,7,11,13,\dots$ thành một dãy chữ số $235711131719\dots$). Kết quả Bình có được sau khi thực hiện công việc trên là một số nguyên $M$. Bình tự hỏi không biết mình có bỏ sót một số nguyên tố nào trong quá trình trên.

Yêu cầu: Cho trước số nguyên $M$, viết chương trình kiểm tra nếu $M$ được tạo ra bằng việc ghép các số nguyên tố liên tiếp bắt đầu từ $2$ thì xuất ra số nguyên tố cuối cùng được ghép vào $M$. Nếu $M$ không được tạo ra theo cách mô tả ở trên thì xuất ra $-1$.

Số nguyên tố cuối cùng phải được ghép đầy đủ: nếu $M$ dừng giữa chừng các chữ số của một số nguyên tố thì $M$ không được tạo ra theo cách trên.

Dữ liệu vào

Một dòng gồm số nguyên dương $M$ (không có chữ số $0$ ở đầu).

Dữ liệu ra

In ra số nguyên tố cuối cùng được ghép vào $M$. Nếu $M$ không được tạo ra bằng cách ghép các số nguyên tố liên tiếp bắt đầu từ $2$ thì in ra $-1$.

Ràng buộc

• $M$ có không quá $500000$ chữ số.

Subtasks

• Subtask 1 ($30\%$ số điểm): $M$ có không quá $26$ chữ số.
• Subtask 2 ($20\%$ số điểm): $M$ có không quá $500$ chữ số.
• Subtask 3 ($50\%$ số điểm): $M$ có không quá $500000$ chữ số.

Ví dụ