An có một xâu \(S\) và muốn tìm xâu con lặp lại dài nhất trong \(S\), tức là xâu con xuất hiện ít nhất hai lần tại các vị trí khác nhau (có thể chồng chéo). Hãy giúp An giải bài toán.

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

• Một dòng duy nhất chứa xâu \(S\) (\(1 \le |S| \le 5000\)), chỉ gồm chữ cái in thường.

Định dạng đầu ra

• In ra độ dài của xâu con lặp lại dài nhất. Nếu không có, in ra 0.

Ví dụ

Input:

ababa

Output:

3

Giải thích: Xâu aba xuất hiện tại vị trí 0 và 2.

Ràng buộc

• 50% số điểm: \(|S| \le 500\).
• 50% số điểm còn lại: \(|S| \le 5000\).