#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = long long;
const int N=200010,c=20;
struct SuffixArray{
    int rk[N],sa[N];//sa[i]为排名第i的后缀起点,rk[i]为s[i,n-1]的排名
    int height[N];//height[i]为排名第i的和排名第i-1的字符串的最长公共前缀
    int n;
    //注意！！！全都是0~n-1的编码
    void intt(string& s){//m为筒的大小(比如小写字母为26),c为基准如'a'/'0'
        n=s.size();
        vector<int> cnt(n);
        vector<pair<char,int>> res(n);
        for(int i=0;i<n;i++)    res[i]={s[i],i};
        sort(res.begin(),res.end());
        for(int i=0;i<n;i++) {sa[i]=res[i].second;}
        int q=0;
        for(int i=0;i<n;i++){
            if(i!=0&&res[i].first!=res[i-1].first)  q++;
            rk[res[i].second]=q;
        }
        for(int k=1;k<n;k<<=1){
            vector<int> tmp(n);
            int p=0;
            for(int i=n-k;i<=n-1;i++)   tmp[p++]=i;
            for(int i=0;i<n;i++){
                if(sa[i]>=k) tmp[p++]=sa[i]-k;  
            }   
            const int maxn=n;
            cnt.assign(maxn,0);
            for(int i=0;i<n;i++)    ++cnt[rk[tmp[i]]];
            for(int i=1;i<maxn;i++) cnt[i]+=cnt[i-1];
            for(int i=n-1;i>=0;i--){
                sa[--cnt[rk[tmp[i]]]]=tmp[i];
            }
            auto new_rk=[&](int x){
                return make_pair(rk[x],(x+k<=n-1?rk[x+k]:-1));
            };
            p=0;
            for(int i=0;i<n;i++){
                if(i==0)    tmp[sa[i]]=p;
                else    tmp[sa[i]]=(new_rk(sa[i-1])==new_rk(sa[i])?p:++p);
            } 
            for(int i=0;i<n;i++)    rk[i]=tmp[i];
            if(p==n)    break;
        }
        int pre=0;
        for(int i=0;i<n;i++){
            if(rk[i]==0)    continue;
            if(pre) pre--;
            int r=sa[rk[i]-1];
            while(r+pre<n&&i+pre<n&&s[r+pre]==s[i+pre]) pre++;
            height[rk[i]]=pre;
        }
    }
    int st[c][N];
    int maxn=0;
    void build_st(){
        while((1<<maxn)<=n) maxn++;
        for(int i=0;i<n;i++){
            st[0][i]=height[i];
        }
        for(int i=1;i<maxn;i++){
            for(int j=0;j<n;j++){
                if(j+(1<<i)<=n) st[i][j]=min(st[i-1][j],st[i-1][j+(1<<(i-1))]);  
            }
        }     
    }
 	int lcp_rk(int x,int y){//排名为x的后缀和排名为y的后缀的最长公共前缀
        if(x>=n||x<0||y>=n||y<0)    return 0;
        if(x>y) swap(x,y);
        if(x==y)    return n-sa[y];
        x++;
        int q=__lg(y-x+1);
        return min(st[q][x],st[q][y-(1<<q)+1]);
    }
    int lcp_pz(int x,int y){
        if(x>=n||x<0||y>=n||y<0)    return 0;
        x=rk[x],y=rk[y];
        if(x>y) swap(x,y);
        if(x==y)    return n-sa[y];
        x++;
        int q=__lg(y-x+1);
        return min(st[q][x],st[q][y-(1<<q)+1]);
    }
    int get(int x,int len,int mo){
        if(mo==0){
            for(int i=maxn-1;i>=0;i--){
                if(x+(1<<i)-1<n&&st[i][x]>=len){
                    x+=(1<<i);
                }
            }
            return x;
        }
        else{
            for(int i=maxn-1;i>=0;i--){
                if(x-(1<<i)+1>=0&&st[i][x-(1<<i)+1]>=len){
                    x-=(1<<i);
                }
            }
            return x;
        }
    }
    pair<int,int> get_le_re(int x,int len){//和排名为x后缀最长公共前缀>=len的(l~r)排名
        return {get(x,len,1),get(x+1,len,0)-1};
    }
};
//runs定义(l,r,len)为r-l+1>=2*len且对于任意x+len<=r&&x>=l有s[x]==s[x+len]且len为最小循环节且runs无法再向左右扩展
//runs的数量为O(n),runs的len总和为O(n)
SuffixArray lcp,lcs;
vector<array<int,3>> get_runs(string& s){
    int sz=s.size();
    string t=s;
    reverse(t.begin(),t.end());
    lcp.intt(s),lcs.intt(t);
    lcp.build_st(),lcs.build_st();
    vector<array<int,3>> runs;
    for(bool flag:{false,true}){
        vector<int> lyn(sz,sz),st;
        for(int i=0;i<sz;i++){
            while(!st.empty()){
                int t=st.back(),k=lcp.lcp_pz(i,t);
                if(i+k<sz&&((s[i+k]>s[t+k])^flag)) break;
                lyn[t]=i;
                st.pop_back();
            }
            st.push_back(i);
        }
        for(int i=0;i<sz;i++){
            int j=lyn[i]-1;
            int le=i-lcs.lcp_pz(sz-i,sz-j-1),re=j+lcp.lcp_pz(i,j+1);
            if(re-le+1>=2*(j-i+1)){
                runs.push_back({le-1,re-1,j-i+1});
            }
        }
    }
    sort(runs.begin(),runs.end());
    runs.erase(unique(runs.begin(),runs.end()),runs.end());
    return runs;
}


const ll M=995053212556338707,p=223;
ll add(ll x,ll y){
    return x+y>=M?x+y-M:x+y;
}
ll del(ll x,ll y){
    return x-y+M>=M?x-y:x-y+M;
}
ll mul(ll x,ll y){
    return (__int128_t)x*y%M;
}
ll h[200010],q[200010];
SuffixArray sf;
void solve(void) {
    string s;
    cin>>s;
    sf.intt(s);
    ll ans=0;
    int sz=s.size();
    for(int i=0;i<sz;i++){
        ans+=sz-sf.sa[i]-sf.height[i];
    }
    cerr<<ans<<'\n';
    s=' '+s;
    for(int i=1;i<=sz;i++){
        q[i]=add(mul(q[i-1],p),s[i]-'a'+1);
    }
    auto get=[&](int l,int r)->ll {
        l++,r++;
        return del(q[r],mul(q[l-1],h[r-l+1]));
    };
    vector<array<int,3>> runs=get_runs(s);
    //本原不同的平方串数量为O(n),以下是O(nlogn)的枚举,因此需要对结果去重
    //方法是暴力枚举所有runs,平方串的长度为2*k*len,暴力枚举k然后枚举起点在[x,x+lz-1]中
    unordered_map<ll,int> mp;
    for(auto [x,y,lz]:runs){
        for(int i=0;i<lz;i++){
            int k=(y-(x+i)+1)/lz;
            ll w=get(x+i,x+i+lz-1);
            ans-=max(0,k-1-mp[w]);
            mp[w]=max(mp[w],k-1);
        }
    }
    cout<<ans<<'\n';
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    h[0]=1;
    for(int i=1;i<=200000;i++)  h[i]=mul(h[i-1],p);
    int _ = 1;
    cin >> _;
    while (_--) solve();

    return 0;
}

/*
1
mxsslrrxtwwnwlsrxxxbsmtxxwwntsbrwlxnbxunutnlmrrlubturuwmbnobrolwunwurtbnmlumxmwtwrsulruxslsnltsstmmxbsmuonroubrnnmu
*/