In his latest 15-122 (Principles of Imperative Computation) homework, Edward learned how to compress strings using prefix-free codes generated by Huffman coding. Although this is a great start, he wonders whether better compression algorithms exist by abusing repetitions in the string. For example, if we define the repeatability of a string $s$ as the maximum integer $k$ such that $s$ is the concatenation of $k$ copies of some string $t$, then it is not hard to see that strings with higher repeatability are easier to compress.

However, using repeatability as a measure of compressibility is not quite perfect: the string aaabaab only has repeatability $1$ but still contains many repetitions. In an attempt to fix this flaw, he defines the compressibility of a string as the sum of the repeatability of all of its substrings. This seems to be a better metric: the compressibility of aaabaab is $34$ while the compressibility of huffman is $29$, even though they both have repeatability $1$.

In order for this metric to be useful though, it remains to find an efficient algorithm that computes the compressibility of any given string $S$. Therefore, your job is to write a program to help him compute the compressibility of $S$.

Constraints

$1\le |S|\le 2\times {10}^5$

$S$ only contains lowercase characters.

Subtask 1 [10%]

$1\le |S|\le 500$

Subtask 2 [20%]

$1\le |S|\le 5\times {10}^3$

Subtask 3 [70%]

No additional constraints.

Input Specification

The first and only line contains a string $S$.

Output Specification

Output the compressibility of $S$ on its own line.

Sample Input

aaabaab

Sample Output

34

Explanation for Sample

There are $23$ substrings of repeatability $1$.

There are $4$ substrings of repeatability $2$, namely $S[0:1]=\text{aa}$, $S[1:2]=\text{aa}$, $S[4:5]=\text{aa}$, and $S[1:6]=\text{aabaab}$.

There is $1$ substring of repeatability $3$, namely $S[0:2]=\text{aaa}$.

Thus, the compressibility can be computed as $23\times 1+4\times 2+1\times 3=34$.