String

类似Hdu3336

给出一个字符串，请算出它的每个前缀分别在字符串中出现了多少次。再将这些结果加起来输出

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

For each test case, just a number means the sum.

Sample Input

3

acacm

moreandmorecold

thisisthisththisisthisisthisththisis

Sample Output

7

19

82

HINT

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

Sol1:利用Kmp的性质,暴力统计,但是会TLE(感觉这种做法是错的)

Sol2:

 推荐使用下面这个进行讲解