Longest String Sequence Construction

Given a string S consisting of lowercase English letters, we define some basic concepts for any string S = s₁s₂…s_n:

• The length of S is \( |S| = n \).
• For two strings S and T = t₁t₂…t_m, we say that T is a substring of S if either m = 0 (i.e. T is the empty string) or there exist indices \(1 \le i \le j \le n\) such that \(T = s_i s_{i+1} \cdots s_j\). In particular, if in the above definition the index \(i\) can be \(1\) then T is a prefix of S, and if \(j\) can be \(n\) then T is a suffix of S.

Now, given the string S, you are required to find a longest possible sequence of strings \( (T_0, T_1, \ldots, T_l) \) such that:

1. \(T_0\) is a substring of \(S\);
2. For every \(1 \le i \le l\), \( |T_i| - |T_{i-1}| = 1 \);
3. For every \(1 \le i \le l\), there exists a substring \(S'_i\) of \(S\) of length \(|T_i|+1\) satisfying:
   • The prefix of \(S'_i\) of length \(|T_{i-1}|\) is exactly \(T_{i-1}\);
   • The suffix of \(S'_i\) of length \(|T_i|\) is exactly \(T_i\).

Your task is to output the maximum possible value of \(l\) (i.e. the maximum number of transitions in such a sequence).

Note: The empty string is considered a substring of any string.

inputFormat

The input consists of a single line containing the string S (comprised of lowercase English letters).

outputFormat

Output a single integer representing the maximum value of \(l\) for a sequence \( (T_0, T_1, \ldots, T_l) \) satisfying the conditions.

sample

ab

1