Bomboslav set up a branding agency and now helps companies to create new logos and advertising slogans. In term of this problems, slogan of the company should be a nonempty substring of its name. For example, if the company name is "hornsandhoofs
", then substrings "sand
" and "hor
" could be its slogans, while strings "e
" and "hornss
" can not.
Sometimes the company performs rebranding and changes its slogan. Slogan \(A\) is considered to be cooler than slogan \(B\) if \(B\) appears in \(A\) as a substring abacaba
" is cooler than slogan \(B\) = "ba
", slogan \(A\) = "abcbcbe
" is cooler than slogan \(B\) = "bcb
", but slogan \(A\) = "aaaaaa
" is not cooler than slogan \(B\) = "aba
".
You are given the company name \(w\) and your task is to help Bomboslav determine the length of the longest sequence of slogans \(s_1, s_2, \ldots, s_k\), such that any slogan in the sequence is cooler than the previous one.
Subtask #  Score  Constraints 

1  5  \(n \leq 50\) 
2  24  \(n \leq 4000\) 
3  17  There exists an \(s_1, s_2, \ldots, s_k\) with maximum \(k\) in which all \(s_1, s_2, \ldots, s_k\) are prefixes of \(w\). 
4  54  No additional constraints 
The input consists of a string of lowercase English letters on a single line, \(w\).
Output a the single integer  the maximum possible length of the sequence of slogans of the company named \(w\), such that any slogan in the sequence (except the first one) is cooler than the previous.
Sample Input 1  Sample Output 1 
qaqaqzz

3

Explanation
\(s_1 =\) qaqaqzz
\(s_2 =\) qaq
\(s_3 =\) q
Sample Input 2  Sample Output 2 
dabcabcabcabca

5

Explanation
\(s_1 =\) abcabcabcabca
\(s_2 =\) abcabcabca
\(s_3 =\) abcabca
\(s_4 =\) abca
\(s_5 =\) a
Sample Input 3  Sample Output 3 
abracadabra

3

Explanation
\(s_1 =\) abracadabra
\(s_2 =\) abra
\(s_3 =\) a
Subtask  Score 

1  5 
2  24 
3  17 
4  54 