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 to c[N-1].
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.