Another easy string problem

Given a string $s$. We call any non-empty string $t$ good, if it is a substring of $s$ and has 4 non-overlapping occurrences in $s$. Your task is to find the number of different good strings.

Input

Contains one string $s(1\le \text{length of s}\le 10^5)$ — given string. It is guaranteed that all letters are lowercase English alphabet.

Output

Print one integer — the number of different good strings.

Examples