Buzzing Professor
At a renowned university, a well-known professor delivered his lectures at such a rapid pace that it was nearly impossible to comprehend anything. Students joked that he wasn't speaking but rather buzzing. Naturally, no one knew much about this enigmatic professor.
Recently, Petya Bulochkin decided to study the professor's vocabulary. To do this, he attended one of the lectures and recorded everything on a tape recorder. Later, at home, Petya played back the recording at one-tenth the speed and managed to write down everything the professor said. However, there was a challenge—despite the slowed-down playback, it was still difficult to pinpoint where the professor paused between words. As a result, Petya ended up with a text (S), consisting solely of lowercase Latin letters, representing the lecture.
Petya is not interested in words that the professor used only once during his lecture. It is evident that if the professor used a particular word two or more times, there must be two non-overlapping occurrences of this word in the text (S). We define a non-empty substring (T) as a candidate word if there are two non-overlapping occurrences of (T) in (S). Petya now wants to identify all substrings that qualify as candidate words, and you are tasked with helping him.
Input
The input consists of a single line containing between 1 and 3000 lowercase Latin letters. This line represents the text (S) that the professor delivered during the lecture.
Output
The output should be a single line containing one number, which is the count of substrings that are candidate words.