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, \dots, 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.

Input

Ghi xâu ~S~.

Output

Ghi ra một số 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~.