Input

T- number of test cases. T<=20; Each test case consists of one string, whose length is <= 50000

Output

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

Example

Input:

CCCCC

ABABA

Output:

Solution

后缀排序后

一个后缀 \(SA[i]\) 有 \(n-SA[i]+1\) 个子串，但后缀 \(SA[i]\) 与 \(SA[i-1]\) 有 \(height[i]\) 个字符相同，那么就有 \(height[i]\) 个子串一样，减去就是了

#include
    
     #define ui unsigned int#define ll long long#define db double#define ld long double#define ull unsigned long longconst int MAXN=50000+10;char s[MAXN];int T,n,m,SA[MAXN],rk[MAXN],cnt[MAXN],nxt[MAXN],height[MAXN];template
     
       inline void read(T &x){    T data=0,w=1;    char ch=0;    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();    if(ch=='-')w=-1,ch=getchar();    while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();    x=data*w;}template
      
        inline void write(T x,char ch='\0'){    if(x<0)putchar('-'),x=-x;    if(x>9)write(x/10);    putchar(x%10+'0');    if(ch!='\0')putchar(ch);}template
       
         inline void chkmin(T &x,T y){x=(y
        
         
           inline void chkmax(T &x,T y){x=(y>x?y:x);}template
          
            inline T min(T x,T y){return x
           
            
              inline T max(T x,T y){return x>y?x:y;}inline void GetSA(){ n=strlen(s+1),m=300; for(register int i=1;i<=n;++i)rk[i]=s[i]; for(register int i=1;i<=m;++i)cnt[i]=0; for(register int i=1;i<=n;++i)cnt[rk[i]]++; for(register int i=1;i<=m;++i)cnt[i]+=cnt[i-1]; for(register int i=n;i>=1;--i)SA[cnt[rk[i]]--]=i; for(register int k=1,ps;k<=n;k<<=1) { ps=0; for(register int i=n-k+1;i<=n;++i)nxt[++ps]=i; for(register int i=1;i<=n;++i) if(SA[i]>k)nxt[++ps]=SA[i]-k; for(register int i=1;i<=m;++i)cnt[i]=0; for(register int i=1;i<=n;++i)cnt[rk[i]]++; for(register int i=1;i<=m;++i)cnt[i]+=cnt[i-1]; for(register int i=n;i>=1;--i)SA[cnt[rk[nxt[i]]]--]=nxt[i]; std::swap(nxt,rk); rk[SA[1]]=1;ps=1; for(register int i=2;i<=n;rk[SA[i]]=ps,++i) if(nxt[SA[i]]!=nxt[SA[i-1]]||nxt[SA[i]+k]!=nxt[SA[i-1]+k])ps++; if(ps>=n)break; m=ps; } for(register int i=1,j,k=0;i<=n;height[rk[i++]]=k) for(k=k?k-1:k,j=SA[rk[i]-1];s[i+k]==s[j+k];++k);}inline int solve(){ int ans=0; for(register int i=1;i<=n;++i)ans+=n-SA[i]+1-height[i]; return ans;}int main(){ read(T); while(T--) { scanf("%s",s+1); GetSA(); write(solve(),'\n'); } return 0;}