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 \leq 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

• Dòng duy nhất chứa xâu \(S\).

Output

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

Example

a14a5ac7a6bb

3

ac5b2c3a7b

4

Scoring

• \(30\%\) số test ứng với \(30\%\) số điểm có: \(n \leq 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