Given a string, we need to find the total number of its distinct substrings.

Input

T- number of test cases. T<=20;

Each test case consists of one string, whose length is <= 1000

Output

For each test case output one number saying the number of distinct substrings.

Example

Sample Input:

2

CCCCC

ABABA

Sample Output:

5

9

Explanation for the testcase with string ABABA: 

len=1 : A,B

len=2 : AB,BA

len=3 : ABA,BAB

len=4 : ABAB,BABA

len=5 : ABABA

Thus, total number of distinct substrings is 9.

 

题意：

为字符串的子串个数

思路：

使用后缀数组解决。

按sa遍历后缀数组，每一个后缀的贡献即为n-sa[i]-lcp[i];

这里的lcp就是你们所说的height

 

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include