Time Limit : 1 Second

Memory Limit : 128 MB

Submission: 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
© 2015 HUST ACMICPC TEAM. All Right Reserved.