You are given a DNA sequence: a string consisting of characters A, C, G, and T. Your task is to find the longest repetition in the sequence. This is a maximum-length substring containing only one type of character.

Input

The only input line contains a string of n characters.

Output

Print one integer: the length of the longest repetition.

Constraints

• 1≤n≤10^6

Example

Input:

ATTCGGGA

Output:

3

Here, we can see that in this problem all we have to do is to find the longest substring containing the same characters.

So, to solve this problem we need to compare adjacent characters to get the longest string containing the same characters.

So, to solve this problem, we need to compare the adjacent characters find the characters that are similar, and keep counting the similar characters in a count variable, finally, we need to update our answer variable and print it.

#include<bits/stdc++.h>
using namespace std;

int main(){
      string s;
      cin >> s;
      int count = 1, answer = 1;
      int n = s.length();
      for(int i=1;i<n-1;i++){
            if(s[i] == s[i-1]){
                   count++;
            }
            else{
                answer = max(answer, count);
                count = 1;
             }
      }

      answer = max(answer, count);
      cout << answer;
}

That's all for this blog, I will see you soon in the next blog.