#include<bits/stdc++.h>
#define N 1000010
#define For(i,a,b) for(register int i=a;i<=b;i++)
using namespace std;
int n,lnk[N],len[N],lst=1,a[N],occ[N],dfn[N];
int nxt[N][26],tot=1,en[N],sz[N],son[N],h[N];
long long ans;
char s[N];
vector<int> go[N];
set<int> pos,val;
inline void insert(int v,int pos)
{
    int nw=++tot,nd=lst;
    len[nw]=len[nd]+1,lst=nw,en[nw]=pos,h[nw]=1;
    while(nd && !nxt[nd][v]) nxt[nd][v]=nw,nd=lnk[nd];
    if(!nd) {lnk[nw]=1;return;}
    int q=nxt[nd][v];
    if(len[q] == len[nd]+1) {lnk[nw]=q;return;}
    int clone=++tot;
    len[clone]=len[nd]+1,lnk[clone]=lnk[q];
    memcpy(nxt[clone],nxt[q],sizeof(nxt[q]));
    while(nd && nxt[nd][v] == q) nxt[nd][v]=clone,nd=lnk[nd];
    return void(lnk[nw]=lnk[q]=clone);
}

inline void prework(int x)
{
    a[dfn[x]=++a[0]]=x,sz[x]=1;
    for(int to:go[x])
    {
        prework(to);
        sz[x]+=sz[to],h[x]+=h[to];
        if(h[to] > h[son[x]]) son[x]=to;
    }
    return;
}

inline void add(int x)
{
    auto it=pos.upper_bound(x);
    int l=0,r=it==pos.end()?0:*it;
    if(it != pos.begin()) l=*(--it);
    if(l && r) {occ[r-l]--;if(!occ[r-l]) val.erase(r-l);}
    if(l) {if(!occ[x-l]) val.insert(x-l);occ[x-l]++;}
    if(r) {if(!occ[r-x]) val.insert(r-x);occ[r-x]++;}
    pos.insert(x);
    return;
}

inline void solve(int x,bool flag)
{
    for(int to:go[x]) if(to^son[x])
        solve(to,false);
    if(son[x]) solve(son[x],true);
    if(en[x]) add(en[x]);
    for(int to:go[x]) if(to^son[x])
    {
        int l=dfn[to],r=dfn[to]+sz[to]-1;
        For(i,l,r) if(en[a[i]]) add(en[a[i]]);
    }for(int v:val) ans-=len[x]/v-len[lnk[x]]/v;
    if(!flag) 
    {
        auto it=pos.begin();
        while(it!=pos.end())
            {int l=*(it++);occ[(*it)-l]--;}
        pos.clear(),val.clear();
    }
    return;
}

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        scanf("%s",s+1),n=strlen(s+1);
        //scanf("%d%s",&n,s+1);
        lst=tot=1,ans=a[0]=0;
        For(i,1,n) insert(s[i]-'a',i);
        For(i,1,tot) ans+=len[i]-len[lnk[i]];
        For(i,2,tot) go[lnk[i]].push_back(i);
        prework(1),solve(1,false);
        printf("%lld\n",ans);
        For(i,1,tot)
        {
            go[i].clear(),dfn[i]=h[i]=a[i]=0;
            son[i]=sz[i]=en[i]=lnk[i]=len[i]=0;
            memset(nxt[i],0,sizeof(nxt[i]));
        }
    }
    return 0;
}