Mật khẩu từ chuỗi lặp

Lan gửi cho thư ký một chuỗi \(S\) và bảo rằng mật khẩu mở tệp chính là số lần xuất hiện của ký tự xuất hiện nhiều nhất trong "ước" của \(S\).

Chuỗi \(X\) là ước của \(S\) nếu \(X\) là chuỗi ngắn nhất mà khi viết nối liên tiếp một số lần ta thu được đúng \(S\). Ví dụ ước của aaaaa là a, ước của abc là abc, ước của ababab là ab.

Cho chuỗi \(S\), hãy tìm mật khẩu.

Input

Một dòng chứa chuỗi \(S\) gồm các ký tự ASCII in được, không có dấu cách.

Output

In ra một số nguyên: số lần xuất hiện lớn nhất của một ký tự trong ước của \(S\).

Constraints

• \(1 \le |S| \le 5000\) (60% số test có \(|S| \le 255\)).

Sample Input

abcabcabca

Sample Output

4