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ừ xâu \(S\) để tạo thành 1 số không quá \(5 \times 10^6\) và là số nguyên tố. Học sinh chọn được số lớn nhất trong các số nguyên tố thỏa mãn điều kiện thì nhận được phần thưởng.

Lưu ý: nếu xâu \(S\) có nhiều đoạn con tạo thành số nguyên tố giống nhau thì chỉ tính một số lớn nhất đó. Nếu không có đoạn nào tạo thành số nguyên tố thì ghi ra 0.

Danh sách các số nguyên tố trong phạm vi \(5 \times 10^6\): \(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ..., 5000099\).

Dữ liệu vào

• Một xâu S có độ dài không quá 5.10^6 ký tự.

Dữ liệu ra

• Số nguyên tố lớn nhất mà học sinh nhận được. Nếu không có thì ghi 0.

Input 1

cd0056aB45k1250cd19hk23

Output 1

23

Input 2

cA12cg42m

Output 2

0

Ràng buộc

• 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\).