Description

We want to know how similar the content of a string is to its prefix. A string could gain a score of k when there is a non-prefix substring of length k that is the same as its prefix. Find the total score for a string.

Input

There are 20 test cases. Each case contains a string of English letters with length n.

\(1 \leq n \leq 10^5\)

Output

Each case one line, the score of the string.

abcabc
aaaa

6
10

Hint

For the first case, “a”, “ab”, “abc” are non-prefix substrings same as prefix and the score is 1+2+3=6.

For the second case, 3 “a”s, 2 “aa”s and 1 “aaa” are non-prefix substrings same as prefix. Then the score is 3+4+3=10.