Sau khi học về bài kiểm tra chuỗi đối xứng trên lớp, do chưa hiểu rõ nên bạn Phú đã lên mạng copy được thuật toán sau trên www.geeksforgeeks.org/ (đoạn code ở cuối bài). Hôm nay trong giờ ôn tập, thầy cho Phú một chuỗi ~s~ gồm các ký tự tiếng Anh in hoa, tuy nhiên chuỗi của thầy có thể không đối xứng nên nhanh chóng ngắt vòng lặp của thuật toán. Phú thì muốn vòng lặp chạy càng lâu càng tốt để bạn có thể debug, quan sát được quá trình chạy và hiểu rõ hơn. Bạn hãy giúp Phú xáo trộn chuỗi ~s~ lại để vòng lặp while có thể chạy được nhiều nhất nhé.

Input

Một chuỗi ký tự duy nhất có độ dài không quá ~10^5~ gồm các ký tự tiếng Anh in hoa.

Output

Số lần lặp nhiều nhất của vòng while.

Sample input

AABBCDEF

Sample output

3

Giải thích

Bạn có thể đảo chuỗi ~s~ lại thành ~ABCDEFBA~, chạy được qua hai vòng lặp đầu, đến vòng thứ ba mới ngắt.

bool isPalindrome(string str) {
    int low = 0;
    int high = str.size() - 1;
    while (low < high) {
        if (str[low] != str[high]) {
            return false; // not a palindrome.
        }
        low++; // move the low index forward
        high--; // move the high index backwards
    }
      return true; // is a palindrome     
}