#include<stdio.h>#include<string.h> #define maxn 100010 int wa[maxn]; int wb[maxn]; int wv[maxn]; int wsa[maxn]; int ranks[maxn],height[maxn];  void calheight(int *r,int *sa,int n) {      int i,j,k=0;      for(i=1;i<=n;i++) ranks[sa[i]]=i;      for(i=0;i<n ;height[ranks[i++]]=k)      for(k?k--:0,j=sa[ranks[i]-1];r[i+k]==r[j+k];k++);      return; }  int cmp(int *r,int a,int b,int l) {     return r[a]==r[b]&&r[a+l]==r[b+l]; };  void da(int *r,int *sa,int n,int m) {      int i,j,p,*x=wa,*y=wb,*t;      for(i=0;i<m;i++) wsa[i]=0;      for(i=0;i<n;i++) wsa[x[i]=r[i]]++;      for(i=1;i<m;i++) wsa[i]+=wsa[i-1];      for(i=n-1;i>=0;i--) sa[--wsa[x[i]]]=i;      for(j=1,p=1;p<n;j*=2,m=p)      {       for(p=0,i=n-j;i<n;i++) y[p++]=i;       for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;       for(i=0;i<n;i++) wv[i]=x[y[i]];       for(i=0;i<m;i++) wsa[i]=0;       for(i=0;i<n;i++) wsa[wv[i]]++;       for(i=1;i<m;i++) wsa[i]+=wsa[i-1];       for(i=n-1;i>=0;i--) sa[--wsa[wv[i]]]=y[i];       for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)       x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;       }       return; }  int r[maxn]; int sa[maxn]; int main() {     char str[maxn];     int t,i;     scanf("%d",&t);     while(t--)     {         scanf("%s",str);         memset(r, 0 ,sizeof(r));         memset(sa, 0, sizeof(sa));         int len = strlen(str);         for (i = 0 ; i < len; ++i)         {             r[i] = (int)str[i];         }         da(r, sa, len + 1 , 150);         calheight(r, sa, len);         int sum = 0;         for(i=0;i<len;i++)             sum += len-sa[i+1]-height[i+1];         printf("%d\n",sum);     }     return 0; }