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 một đoạn con liên tiếp chỉ gồm các chữ số để tạo thành một số không quá ~5 \times 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ất để nhận được nhiều tiền thưởng nhất có thể.

Ví dụ: ~S =~ cd0056a845k1250cd19hk23, ta có thể tạo ra các số như: ~0, 00, 005, 0056, 0, 05, 056, 5, 564, 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~.

Dữ liệu đầu vào

Gồm một xâu ~S~ có độ dài không quá ~5 \times 10^6~ kí tự.

Dữ liệu đầu ra

Gồm 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~.

Ràng buộc dữ liệu

• 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 \times 10^6~, số nguyên tố lớn nhất tạo được ~\le 5 \times 10^6~.

Ví dụ

Ví dụ 1

INPUT

cd0056aB45k1250cd19hk23

OUTPUT

23

Ví dụ 2

INPUT

cA1cg4m

OUTPUT

0