Cho xâu ~S~ chỉ gồm các chữ cái Latinh in thường. Một xâu con liên tiếp ~X~ của ~S~ được gọi là có tần số xuất hiện cao nếu tồn tại một ký tự trong ~X~ có số lần xuất hiện nhiều hơn tổng số lần xuất hiện của tất cả ký tự còn lại.

Yêu cầu

Tìm độ dài lớn nhất của một xâu con có tần số xuất hiện cao.

Input

Một dòng chứa xâu ~S~ chỉ gồm các chữ cái a đến z, độ dài không quá ~2\times 10^5~.

Output

In ra độ dài lớn nhất tìm được.

Subtask

• Có ~30\%~ số test ứng với ~30\%~ số điểm: ~S~ chỉ gồm các ký tự thuộc tập ~\{a,b,c\}~ và ~|S| \le 2\times 10^3~.
• Có ~30\%~ số test ứng với ~30\%~ số điểm: ~S~ chỉ gồm chữ cái Latinh in thường và ~|S| \le 2\times 10^3~.
• Có ~40\%~ số test ứng với ~40\%~ số điểm: ~S~ chỉ gồm chữ cái Latinh in thường và ~|S| \le 2\times 10^5~.

Ví dụ 1

aaa

3

Ví dụ 2

ababab

5