Xâu nguyên tố cùng nhau

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à số 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.

Trong tệp sprime.inp ghi xâu $S$.

Ghi ra tệp sprime.out 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$.

• 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 đề là số nguyên tố;
• 30% số test ứng với 30% số điểm không có ràng buộc thêm.