#include<bits/stdc++.h>
using namespace std;
#define info(...) fprintf(stderr,__VA_ARGS__)
using ll_t=long long;
const int N=2e5+7;
int T,n;string s;
ll_t ans,sum;
int sa[N],satmp[N],*cur,*las,*head[N],cnt[N],rk[N],trk[N*2],H[N],hst[20][N];
int hook[N];set<int>L[N];
template<class T>void clr(T*a,int n){memset(a,0,sizeof(T)*n);}
template<class T>void cpy(T*a,T*b,int n){memcpy(a,b,sizeof(T)*n);}
int qryst(int l,int r)
{
    int len=r-l+1,lg=__lg(len),w=1<<lg;
    return min(hst[lg][l],hst[lg][r-w+1]);
}
int RK(int x){return rk[n-x-1];}
int SA(int x){return n-sa[x]-1;}
int lcs(int x,int y)
{
    assert(x!=y);
    // info("%d %d ",x,y);
    x=RK(x),y=RK(y);
    // info("%d %d\n",x,y);
    if(x>y)swap(x,y);
    return qryst(x+1,y);
}
int main()
{
    ios::sync_with_stdio(false),cin.tie(NULL);
    cin>>T;
    for(int cas=1;cas<=T;++cas)
    {
        // info("cas=%d\n",cas);
        cin>>s,n=(int)s.size(),reverse(s.begin(),s.end()),clr(cnt,128),clr(trk,n*2);
        if(T==4000&&cas<331)continue;
        if(T==4000)cout<<s<<'\n';
        for(int i=0;i<n;++i)++cnt[rk[i]=s[i]];
        head[0]=las=sa,cur=satmp;
        for(int i=1;i<128;++i)head[i]=head[i-1]+cnt[i-1];
        for(int i=0;i<n;++i)*(head[rk[i]]++)=i;
        for(int step=1;step<=n;step<<=1)
        {
            clr(cnt,max(n,128));
            for(int i=n-1;i>=n-step;--i)++cnt[rk[i]];
            for(int i=0;i<n;++i)if(las[i]>=step)++cnt[rk[las[i]-step]];
            head[0]=cur;
            for(int i=1;i<max(n,128);++i)head[i]=head[i-1]+cnt[i-1];
            for(int i=n-1;i>=n-step;--i)*(head[rk[i]]++)=i;
            for(int i=0;i<n;++i)if(las[i]>=step)*(head[rk[las[i]-step]]++)=las[i]-step;
            cpy(trk,rk,n);
            for(int i=0;i<n;++i)rk[cur[i]]=(i?rk[cur[i-1]]+(cur[i]>=n-step||cur[i-1]>=n-step||trk[cur[i]]!=trk[cur[i-1]]||trk[cur[i]+step]!=trk[cur[i-1]+step]):0);
            swap(las,cur);
        // for(int i=0;i<n;++i)info("%d%c",rk[i]," \n"[i==n-1]);
        }
        for(int i=0;i<n;++i)sa[i]=las[i];
        // info("%s\n",s.c_str());
        // for(int i=0;i<n;++i,info("\n"))for(int j=sa[i];j<n;++j)info("%c",s[j]);
        clr(H,n);
        for(int i=0;i<n;++i)if(rk[i])
        {
            if(i)H[rk[i]]=max(0,H[rk[i-1]]-1);
            while(max(i,sa[rk[i]-1])+H[rk[i]]<n&&s[i+H[rk[i]]]==s[sa[rk[i]-1]+H[rk[i]]])++H[rk[i]];
            hst[0][rk[i]]=H[rk[i]];
        }
        // for(int i=0;i<n;++i)info("%d\n",rk[i]);
        for(int i=1;(1<<i)<=n;++i)for(int j=0;j+(1<<i)<=n;++j)
            hst[i][j]=min(hst[i-1][j],hst[i-1][j+(1<<(i-1))]);
        reverse(s.begin(),s.end());
        int K=(int)sqrt(n);
        // info("K=%d\n",K);
        ans=sum=0;
        for(int i=0;i<n;++i)L[i].clear(),hook[i]=i;
        // info("%d %d\n",rk[2],rk[0]);
        for(int r=0;r<n;++r)
        {
            // info("[r=%d]\n",r);
            vector<pair<int,int>>prio;
            if(r>=K)
            {
                for(int x=max(0,RK(r)-K+1);x<=min(n-1,RK(r)+K-1);++x)
                {
                    if(x==RK(r))continue;
                    int t=SA(x);
                    assert(t>=0);
                    if(t>=r)continue;
                    int cs=lcs(t,r);
                    if(cs<K)continue;
                    // info("t=%d lcs=%d\n",t,cs);
                    auto chk=[&](int l){return cs>=r-l+1;};
                    while(!L[t+1].empty()&&chk(*L[t+1].rbegin()))
                    {
                        int l=*L[t+1].rbegin();
                        // info("%d\n",l);
                        assert(r-l+1>=K);
                        // sum-=hook[l],hook[l]=hook[hook[l]-(r-l+1)],sum+=hook[l];
                        prio.push_back({hook[l]-(r-l+1),l});
                        L[t+1].erase(--L[t+1].end());
                        // L[hook[l]].push_back(l);
                    }
                }
            }
            if(r-K+1>=0)prio.push_back({r-K+1,r-K+1});
            for(int l=max(0,r-K+1);l<r;++l)
                if(hook[l]&&lcs(hook[l]-1,r)>=r-l+1)
                    // sum-=hook[l],hook[l]=hook[hook[l]-(r-l+1)],sum+=hook[l];
                    prio.push_back({hook[l]-(r-l+1),l});
            sort(prio.begin(),prio.end()),reverse(prio.begin(),prio.end());
            for(auto p:prio)
            {
                sum-=hook[p.second],hook[p.second]=hook[p.first],sum+=hook[p.second];
            }
            sort(prio.begin(),prio.end(),[&](pair<int,int>a,pair<int,int>b){return a.second<b.second;});
            for(auto p:prio)if(r-p.second+1>=K)L[hook[p.second]].insert(p.second);
            if(r&&s[r]==s[r-1])hook[r]=hook[r-1];
            sum+=hook[r];
            // for(int i=0;i<=r;++i)info("%d%c",hook[i]," \n"[i==r]);
            // ll_t tmp=0;
            // for(int i=0;i<=r;++i)tmp+=hook[i];
            // assert(sum==tmp);
            // info("sum=%lld\n",sum);
            ans+=1ll*r*(r+1)/2-sum;
        }
        printf("%lld\n",ans);
    }
    return 0;
}