Cho xâu \(S\), tìm độ dài của cặp xâu con dài nhất gồm hai phần có chung tiền tố (xoay vòng). Tức là \(S[l..r]\) và \(S[r+1..n-1]\) có LCP lớn nhất.

Định dạng đầu vào

• Một dòng chứa xâu \(S\) (\(1 \le |S| \le 10^5\)).

Định dạng đầu ra

• Một số nguyên là độ dài LCP lớn nhất giữa hai phần xâu được xoay vòng.

Ví dụ

Input:

abcabcx

Output:

3

Ràng buộc

• 100% số điểm: \(|S| \le 10^5\).