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 as the maximum integer such that is the concatenation of copies of some string , 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 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 while the compressibility of `huffman`

is , even though they both have repeatability .

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

#### Constraints

only contains lowercase characters.

##### Subtask 1 [10%]

##### Subtask 2 [20%]

##### Subtask 3 [70%]

No additional constraints.

#### Input Specification

The first and only line contains a string .

#### Output Specification

Output the compressibility of on its own line.

#### Sample Input

`aaabaab`

#### Sample Output

`34`

#### Explanation for Sample

There are substrings of repeatability .

There are substrings of repeatability , namely , , , and .

There is substring of repeatability , namely .

Thus, the compressibility can be computed as .

## Comments