Cho chuỗi ký tự S chỉ gồm các chữ cái latin thường từ 'a' đến 'z'.

Một chuỗi con liên tiếp X của S được gọi là chuỗi có mật độ xuất hiện cao nếu tồn tại một ký tự xuất hiện trong X với số lần lớn hơn tổng số lần xuất hiện của tất cả các ký tự còn lại trong X.

Nói cách khác, nếu trong X có một ký tự xuất hiện k lần và độ dài của X là len, thì:

[ k > len - k ]

Ví dụ

• Với S = "abbbabced":

  • Chuỗi con X = "abbbabc" là chuỗi có mật độ xuất hiện cao vì ký tự 'b' xuất hiện 4 lần, các ký tự còn lại xuất hiện tổng cộng 3 lần.
  • Chuỗi X = "abbbabce" không thỏa mãn vì ký tự xuất hiện nhiều nhất là 'b' có 4 lần, bằng với tổng số lần xuất hiện của các ký tự còn lại (4 lần).

Yêu cầu

Hãy tìm độ dài lớn nhất của một chuỗi con liên tiếp của S có mật độ xuất hiện cao.

Input

Gồm một dòng chứa chuỗi S (1 ≤ |S| ≤ 2 × 10^5).

Output

In ra một số nguyên duy nhất là độ dài lớn nhất của chuỗi con thỏa mãn điều kiện.

Sample Input 1

abbbabced

Sample Output 1

7

Giải thích

Có thể chọn:

• "abbbabc"
• "bbbabce"

đều có độ dài 7.

Sample Input 2

ababab

Sample Output 2

5

Sample Input 3

abc

Sample Output 3

1

Giới hạn

• 30% số test: S chỉ gồm các ký tự thuộc tập {a, b, c} và |S| ≤ 2 × 10^3
• 30% số test: |S| ≤ 2 × 10^3
• 40% số test: |S| ≤ 2 × 10^5