Problem Brief

Maximize Repeated Substring Length

You are given a string S, consisting of lowercase Latin letters and/or question marks (?), your goal is to replace each question mark with any lowercase Latin letter (from 'a' to 'z') in such a way that the length of the longest repeated substring is maximized.

- A repeated substring is a segment/substring of even length within the string where the first half is identical to the second half.

- A substring is any contiguous portion of the string.

Objective: Replace each question mark in the string S with lowercase Latin letters to create the longest possible repeated substring.

Input Format

The only line of input contains a string S, consisting only of lowercase Latin letters and/or question marks.

Output Format

Print a single integer, the maximum length of the longest repeated substring as you replace each question mark in the string with some lowercase Latin letter.

1Example 1

Input

s = "a??a"

Output

Explanation

Draft autosaves locally

public int maximizeRepeatedSubstringLength(String s) {
  // write your code here
}

Input

"a??a"

Output