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 non-empty 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\) = "
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.
|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|
|Sample Input 2||Sample Output 2|
|Sample Input 3||Sample Output 3|