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:

 推薦使用下面這個進行講解