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~.