#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=2e5+5,b1=19491001,P=b1,b2=13331,mod=998244353;
int n,top,st[N];
ll pw1[N],pw2[N];
string a;
vector<array<int,3>>ans;
inline ll md(ll x){return x<mod?x:x-mod;}
struct Hash{
    ll a,b;
    Hash(){a=b=0;}
    Hash(int x){a=b=x%mod;}
    Hash(ll x,ll y){a=x,b=y;}
    inline Hash operator+(const Hash&t){return Hash(md(a+t.a),md(b+t.b));}
    inline Hash operator-(const Hash&t){return Hash(md(a-t.a+mod),md(b-t.b+mod));}
    inline Hash operator*(const int&t){return Hash(a*pw1[t]%mod,b*pw2[t]%mod);}
    inline bool operator==(const Hash&t){return a==t.a&&b==t.b;}
}H[N];
struct Hash_table{
    int sz,h[P],nxt[P*2];
    ll val[P*2];
    void ins(const ll&t) {
        int x=(t+5398+114514)%P;
        for(int i=h[x];i;i=nxt[i])if(val[i]==t)return;
        val[++sz]=t,nxt[sz]=h[x],h[x]=sz;
    }
    void clr() {
        for(int i=1;i<=sz;i++) {
            int x=(val[i]+5398+114514)%P;
            h[x]=nxt[i]=val[i]=0;
        }sz=0;
    }
}mp;
Hash getH(int l,int r){return H[r]-H[l-1]*(r-l+1);}
int lcp(int x,int y) {
    if(a[x]!=a[y])return 0;
    int l=1,r=n-max(x,y)+1,mid,res=0;
    while(l<=r)mid=l+r>>1,getH(x,x+mid-1)==getH(y,y+mid-1)?res=mid,l=mid+1:r=mid-1;
    return res;
}
int lcs(int x,int y) {
    if(a[x]!=a[y])return 0;
    int l=1,r=min(x,y),mid,res=0;
    while(l<=r)mid=l+r>>1,getH(x-mid+1,x)==getH(y-mid+1,y)?res=mid,l=mid+1:r=mid-1;
    return res;
}
bool cmp(int x,int y) {
    int l=lcp(x,y);
    if(max(x,y)+l>n)return x>y;
    return a[x+l]<a[y+l];
}
struct SAM{
    int lst,sz,ch[N*2][26],fa[N*2],len[N*2];
    void ins(int c) {
        int pos=++sz,p=lst,q;len[pos]=len[lst]+1;
        while(p!=-1&&!ch[p][c])ch[p][c]=pos,p=fa[p];
        if(p!=-1) {
            q=ch[p][c];
            if(len[q]==len[p]+1)fa[pos]=q;
            else {
                int cl=++sz;memcpy(ch[cl],ch[q],sizeof(ch[q]));
                len[cl]=len[p]+1,fa[cl]=fa[q],fa[q]=fa[pos]=cl;
                while(p!=-1&&ch[p][c]==q)ch[p][c]=cl,p=fa[p];
            }
        }lst=pos;
    }
    ll slv() {
        for(int i=0;i<=sz;i++)memset(ch[i],0,sizeof(ch[i])),len[i]=fa[i]=0;
        ll ans=0;lst=sz=0,fa[0]=-1;
        for(int i=1;i<=n;i++)ins(a[i]-'a');
        for(int i=1;i<=sz;i++)ans+=len[i]-len[fa[i]];
        return ans;
    }
}S;
void solve() {
    cin>>a,n=a.size(),a=' '+a,mp.clr(),top=0,ans.clear();
    for(int i=1;i<=n;i++)H[i]=H[i-1]*1+Hash(a[i]);
    for(int i=n;i;i--) {
        while(top&&cmp(st[top],i))top--;
        if(top) {
            int j=st[top]-1,p=j-i+1,r=j+lcp(i,j+1),l=i-lcs(i-1,j);
            if(r-l+1>=2*p)ans.push_back({l,r,p});
        }
        st[++top]=i;
    }
    top=0;
    for(int i=n;i;i--) {
        while(top&&cmp(i,st[top]))top--;
        if(top) {
            int j=st[top]-1,p=j-i+1,r=j+lcp(i,j+1),l=i-lcs(i-1,j);
            if(r-l+1>=2*p)ans.push_back({l,r,p});
        }
        st[++top]=i;
    }
    sort(ans.begin(),ans.end()),ans.erase(unique(ans.begin(),ans.end()),ans.end());
    for(auto t:ans) {
        int l=t[0],r=t[1],p=t[2];
        for(int i=l;i<=l+p-1;i++)for(int j=i+p;j+p-1<=r;j+=p) {
            Hash v=getH(i,j-1);
            mp.ins(v.a*mod+v.b);
        }
    }
    cout<<S.slv()-mp.sz<<'\n';
}
int main() {
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    pw1[0]=pw2[0]=1;
    for(int i=1;i<=2e5;i++)pw1[i]=pw1[i-1]*b1%mod,pw2[i]=pw2[i-1]*b2%mod;
    int tt;cin>>tt;
    while(tt--)solve();
    return 0;
}