1328  String
Time Limit : 1 Second
Memory Limit : 128 MB
Submission: 690
Solved: 154
 Description
 Give you a string S,assume the SubString 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 SubString Stri in S, now please calculate the sum of c[0] to c[N1].
 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