#include<cstdio>

#include<cstring>

#include<iostream>

using namespace std;

int ws1[],wv[],wa[],wb[];

int rank[],height[],sa[];

char str[];

int cmp(int *r,int a,int b,int l)

{

    return r[a]==r[b] && r[a+l]==r[b+l];

}

void da(char *r,int *sa,int n,int m)

{

    int i,j,p,*x=wa,*y=wb,*t;

    for(i=;i<m;i++)

        ws1[i]=;

    for(i=;i<n;i++)

        ws1[x[i]=r[i]]++;

    for(i=;i<m;i++)

        ws1[i]+=ws1[i-];

    for(i=n-;i>=;i--)

        sa[--ws1[x[i]]]=i;

    for(j=,p=;p<n;j*=,m=p)

    {

        for(p=,i=n-j;i<n;i++)

            y[p++]=i;

        for(i=;i<n;i++)

            if(sa[i]>=j)

                y[p++]=sa[i]-j;

        for(i=;i<n;i++)

            wv[i]=x[y[i]];

        for(i=;i<m;i++)

            ws1[i]=;

        for(i=;i<n;i++)

            ws1[wv[i]]++;

        for(i=;i<m;i++)

            ws1[i]+=ws1[i-];

        for(i=n-;i>=;i--)

            sa[--ws1[wv[i]]]=y[i];

        for(t=x,x=y,y=t,p=,x[sa[]]=,i=;i<n;i++)

            x[sa[i]]=cmp(y,sa[i-],sa[i],j)?p-:p++;

    }

}

void calheight(char *r,int *sa,int n)

{

    int i,j,k=;

    for(i=;i<=n;i++)

        rank[sa[i]]=i;

    for(i=;i<n;height[rank[i++]]=k)

        for(k?k--:,j=sa[rank[i]-];r[i+k]==r[j+k];k++) ;

}

int main()

{

    int len,i,T;

    long long res;

    scanf("%d",&T);

    getchar();

    while(T--)

    {

        scanf("%s",str);

        len=strlen(str);

        str[len]=;

        da(str,sa,len+,);

        calheight(str,sa,len);

        res=;

        for(i=;i<=len;i++)

            res=res+len-sa[i]-height[i];

        printf("%lld\n",res);

    }

    return ;

}