1328 - String

Time Limit: 1s Memory Limit: 128MB

Submissions: 690 Solved: 154
Description
Give you a string S,assume the Sub-String Stri = S[0..i] and the length of the string is N. e.g. S = "moreandmorecold", N = 15, Str0 = "m" Str1 = "mo" Str2 = "mor" and so on. And we define c[i] indicate how many Sub-String Stri in S, now please calculate the sum of c[0] to c[N-1].
Input
The first line include a number T, means the number of test cases. For each test case, just a line only include lowercase indicate the String S, the length of S will less than 100000.
Output
Fore each test case, just a number means the sum.
Sample Input
3
acacm
moreandmorecold
thisisthisththisisthisisthisththisis
Sample Output
7
19
82

For the first case,
there are two "a","ac" and one "aca","acac","acacm" in the string "acacm".
So the answer is 2 + 2 + 1 + 1 + 1 = 7
Hint
Source
Zehua Hong