Cho một xâu ký tự ~S~ chỉ gồm các chữ cái la tinh in thường từ ~a~, ..., ~z~. Một xâu con ~X~ (gồm các ký tự ở vị trí liên tiếp) của S được gọi là một xâu có tần số xuất hiện cao nếu trong xâu ~X~ có một ký tự bất kỳ nào đó mà số lần xuất hiện của ký tự đó nhiều hơn tổng số lần xuất hiện của các ký tự còn lại trong ~X~.

Ví dụ:

• Với ~S =~ abbbabced, xâu con ~X =~ abbbabc là một xâu con tần số xuất hiện cao, vì ký tự ~b~ xuất hiện ~4~ lần, tổng số lần xuất hiện các ký tự còn lại bằng ~3~ (~a~ xuất hiện ~2~ lần, ~c~ xuất hiện ~1~ lần).

Nếu ~X =~ abbbabce, ký tự ~b~ xuất hiện nhiều lần nhất là ~4~ lần và tổng số lần xuất hiện của các ký tự còn lại cũng bằng ~4~ (~a~ xuất hiện ~2~ lần, ~c~ xuất hiện ~1~ lần, ~e~ xuất hiện ~1~ lần). Do vậy, ~X =~ abbbabce không phải là một xâu con tần số xuất hiện cao.

Yêu cầu: Tìm xâu con ~X~ (gồm các ký tự ở vị trí liên tiếp) của ~S~ là một xâu có tần số xuất hiện cao và có độ dài lớn nhất.

Input

Gồm một xâu ~S~ chỉ gồm các ký tự chữ cái la tinh in thường và có độ dài không lớn hơn ~2 \times 10^5~.

Output

Một số nguyên duy nhất là độ dài của xâu ~X~ tìm được.

Sample Input

aaa
ababb

Sample Output

3
5

Giải thích

Với aaa: ta có thể chọn xâu ~X~ thỏa mãn là aaa (ký tự ~a~ chiếm toàn bộ).

Với ababb: ta có thể chọn ~X =~ ababa vì ký tự ~a~ xuất hiện ~3~ lần, số ký tự còn lại là ~2~, hoặc ~X =~ babab vì ký tự ~b~ xuất hiện ~3~ lần, số ký tự còn lại là ~2~. Độ dài lớn nhất là ~5~.

Subtask

Có ~30\%~ số test ứng với ~30\%~ số điểm thỏa mãn: xâu ~S~ chỉ gồm các ký tự thuộc tập ~{a, b, c}~ và có độ dài ~\le 2 \times 10^3~.

Có ~30\%~ số test ứng với ~30\%~ số điểm thỏa mãn: xâu ~S~ chỉ gồm các ký tự chữ cái la tinh in thường và có độ dài ~\le 10^4~.

Có ~40\%~ số test ứng với ~40\%~ số điểm còn lại: xâu ~S~ chỉ gồm các ký tự chữ cái la tinh in thường và có độ dài ~\le 2 \times 10^5~.