Số nguyên tố

Trong giờ Tin học của lớp 9A thầy Minh có đưa ra một trò chơi trúng thưởng như sau:

Thầy viết lên bảng một xâu S, bạn nào tìm ra số nguyên tố lớn nhất có trong xâu S sẽ nhận được phần thưởng.

Yêu cầu: Xâu S gồm n ký tự chỉ chứa chữ cái và chữ số, học sinh cần chọn 1 đoạn con liên tiếp chỉ gồm các chữ số để tạo thành 1 số không quá $5.10^6$ và là số nguyên tố. Học sinh chọn được số nguyên tố lớn nhất sẽ được tặng thưởng số tiền bằng đúng số được chọn. Bạn hãy giúp các học sinh chọn ra số nguyên tố lớn nhất để nhận được nhiều tiền thưởng nhất có thể.

Ví dụ: S = 'cd0056aB45k1250cd19hk23', ta có thể tạo ra các số như: 0, 00, 005, 0056, 0, 05, 056,5,56, 6, 4, 45,5…… tuy nhiên chỉ có các số 2, 3, 5, 19, 23 là các số nguyên tố, nên số tiền nhận được là 23.

Từ tệp BAI02.INP chứa một xâu S có độ dài không quá $5.10^6$ ký tự.

Ghi ra tệp BAI02.OUT một số nguyên là số tiền mà học sinh nhận được. Nếu không có số nguyên tố nào thì số tiền nhận được là 0.

• 75% test ứng với 75% số điểm với $1 \le N \le 255$, số nguyên tố lớn nhất tạo được $\le 10^6$;
• 25% test ứng với 25% số điểm với $N \le 5.10^6$, số nguyên tố lớn nhất tạo được $\le 5.10^6$.