Buzzing Professor#2464

Buzzing Professor

1 second
64 megabytes
Easy

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 — the professor spoke so fast that even with the slowed playback, it was still difficult to determine exactly where he paused between words. As a result, Petya ended up with a text , 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 . Define a non-empty substring to be a candidate word if there are two non-overlapping occurrences of in . 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 and lowercase Latin letters. This line represents the text that the professor delivered during the lecture.

Output

The output should be a single line containing one number, the count of substrings that are candidate words.

Examples

Example 1

Loading
Loading