#include<bits/stdc++.h>

using namespace std;

#define il inline

#define gc getchar()

#define ri register int

#define rb register bool

#define rc register char

#define rp(i,x,y) for(ri i=x;i<=y;++i)

#define my(i,x,y) for(ri i=x;i>=y;--i)

const int N=+;

int x[N],y[N],sa[N],rk[N],t[N],n,as;

char ch[N];

il int read()

{

    rc ch=gc;ri x=;rb y=;

    while(ch!='-' && (ch>'' || ch<''))ch=gc;

    if(ch=='-')ch=gc,y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;

    return y?x:-x;

}

il bool cmp(ri gd,ri gs,ri k){return y[gd]==y[gs] && y[gd+k]==y[gs+k];}

il void SA()

{

    ri m=,h=;

    rp(i,,n)++t[x[i]=ch[i]-'A'+];

    rp(i,,m)t[i]+=t[i-];

    my(i,n,)sa[t[x[i]]--]=i;

    for(ri k=;k<=n;k<<=)

    {

        ri p=;

        rp(i,,n)y[i]=;rp(i,,m)t[i]=;

        rp(i,n-k+,n)y[++p]=i;rp(i,,n)if(sa[i]>k)y[++p]=sa[i]-k;

        rp(i,,n)++t[x[y[i]]];

        rp(i,,m)t[i]+=t[i-];

        my(i,n,)sa[t[x[y[i]]]--]=y[i];

        swap(x,y);

        x[sa[]]=p=;

        rp(i,,n)x[sa[i]]=cmp(sa[i],sa[i-],k)?p:++p;

        if(p>=n)break;m=p;

    }

    rp(i,,n)rk[sa[i]]=i;

    rp(i,,n)

    {

        if(h)--h;

        while(ch[i+h]==ch[sa[rk[i]-]+h])++h;

        as-=h;

    }

}

int main()

{

    ri T=read();

    while(T--)

    {

        memset(x,,sizeof(x));memset(y,,sizeof(y));memset(t,,sizeof(t));memset(sa,,sizeof(sa));memset(rk,,sizeof(rk));

        scanf("%s",ch+);n=strlen(ch+);as=n*(n+)/;SA();printf("%d\n",as);

    }

    return ;

}