#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct SuffixArray{
    vector<int> rk,sa;//sa[i]为排名第i的后缀起点,rk[i]为s[i,n-1]的排名
    vector<int> height;//height[i]为排名第i的和排名第i-1的字符串的最长公共前缀
    int n;
    //注意！！！全都是0~n-1的编码
    void intt(string& s){//m为筒的大小(比如小写字母为26),c为基准如'a'/'0'
        n=s.size();
        rk.resize(n),sa.resize(n);
        vector<int> cnt(n);
        height.resize(n+1);
        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);
            } 
            rk=tmp;
            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;
        }
    }
    vector<vector<int>> st;
    int maxn=0;
    void build_st(){
        maxn=0;
        while((1<<maxn)<=n) maxn++;
        st.resize(n);
        for(int i=0;i<n;i++){
            st[i].resize(maxn);
            st[i][0]=height[i];
        }
        for(int i=1;i<maxn;i++){
            for(int j=0;j<n;j++){
                if(j+(1<<i)<=n) st[j][i]=min(st[j][i-1],st[j+(1<<(i-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[x][q],st[y-(1<<q)+1][q]);
    }
    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[x][q],st[y-(1<<q)+1][q]);
    }
};
//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,re,j-i+1});
            }
        }
    }
    sort(runs.begin(),runs.end());
    runs.erase(unique(runs.begin(),runs.end()),runs.end());
    return runs;
}


const ll p1=1331,p2=13331,M1=1000000007,M2=998244353;
ll h1[200010],h2[200010],q1[200010],q2[200010];
void solve(void) {
    string s;
    cin>>s;
    SuffixArray sf;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];
    }
    s=' '+s;
    for(int i=1;i<=sz;i++){
        q1[i]=(q1[i-1]*p1%M1+s[i]-'a'+1)%M1,q2[i]=(q2[i-1]*p2%M2+s[i]-'a'+1)%M2;
    }
    auto get=[&](int l,int r)->pair<int,int> {
        l++,r++;
        return {((q1[r]-q1[l-1]*h1[r-l+1]%M1)%M1+M1)%M1,((q2[r]-q2[l-1]*h2[r-l+1]%M2)%M2+M2)%M2};
    };
    vector<array<int,3>> runs=get_runs(s);
    //本原不同的平方串数量为O(n),以下是O(nlogn)的枚举,因此需要对结果去重
    //方法是暴力枚举所有runs,平方串的长度为2*k*len,暴力枚举k然后枚举起点在[x,x+lz-1]中
    map<pair<int,int>,int> mp;
    for(auto [x,y,lz]:runs){
        for(int i=0;i<lz;i++){
            int k=(y-(x+i)+1)/lz;
            pair<ll,ll> w=get(x+i,x+i+lz-1);
            ans-=k-1-mp[w];
            mp[w]=k-1;
        }
    }
    cout<<ans<<'\n';
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    h1[0]=h2[0]=1;
    for(int i=1;i<=200000;i++)  h1[i]=h1[i-1]*p1%M1,h2[i]=h2[i-1]*p2%M2;
    int _ = 1;
    cin >> _;
    while (_--) solve();

    return 0;
}

/*
6
rikkasuggeststoallthecontestants
thisisaproblemdesignedforgrandmasters 
ifyoudidnotachievethat 
youdbetterskiptheproblem
wishyouahighrank
enjoytheexperience

*/