Cho xâu \(S\). Tìm xâu con xuất hiện nhiều lần nhất trong xâu và đếm số lần xuất hiện (có thể overlap).

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

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

Định dạng đầu ra

• Một số nguyên là số lần xuất hiện nhiều nhất của một xâu con nào đó.

Ví dụ

Input:

abab

Output:

3

Giải thích: Xâu ab xuất hiện 3 lần: tại 0, 1, 2 (kể cả overlap).

Ràng buộc

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