Cho xâu ~S~ chỉ có các kí tự chữ cái và kí tự chữ số có độ dài không vượt quá ~10^6~ kí tự. Các số trong xâu ~S~ là một dãy các kí tự chữ số liên tiếp được phân tách bởi các kí tự chữ cái, xâu ~S~ bắt đầu bằng một kí tự chữ cái và kết thúc cũng bằng một kí tự chữ cái. Khi thực hiện lấy ra các số trong ~S~, ta thu được một dãy số ~A~ gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(0 < a_i \le 10^6)~.

Hai số nguyên dương ~x, y~ được gọi là nguyên tố cùng nhau nếu ước chung lớn nhất của chúng bằng ~1~. Một đoạn con liên tiếp trong dãy ~A~ được gọi là nguyên tố cùng nhau nếu mọi cặp số trong đoạn đó là nguyên tố cùng nhau.

Yêu cầu

Tìm đoạn con liên tiếp nguyên tố cùng nhau dài nhất.

Dữ liệu đầu vào

Gồm một dòng duy nhất ghi xâu ~S~.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là độ dài của đoạn con liên tiếp nguyên tố cùng nhau dài nhất của dãy ~A~.

Ràng buộc dữ liệu

• 30% số test ứng với 30% số điểm có: ~n \le 20~.
• 40% số test ứng với 40% số điểm có: các số nguyên xuất hiện trong xâu ~S~ đều là số nguyên tố.
• 30% số test ứng với 30% số điểm không có ràng buộc thêm.

Ví dụ

Ví dụ 1

INPUT

a14a5ac7a6bb

OUTPUT

3

Giải thích: Thực hiện tách các số trong xâu ~S~ ta thu được dãy ~A~ gồm các số ~14, 5, 7, 6~. Đoạn con liên tiếp nguyên tố cùng nhau dài nhất là đoạn: ~5, 7, 6~ có độ dài bằng ~3~.

Ví dụ 2

INPUT

ac5b2c3a7b

OUTPUT

4

Giải thích: Dãy thu được gồm các số ~5, 2, 3, 7~ đều là các số nguyên tố phân biệt nên là nguyên tố cùng nhau, có độ dài bằng ~4~.