#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef vector<int> vi;
typedef pair<int,int> pi;

namespace RUNS{
    const int base=36634229, P=998244353;
    vector< array<int,3> > get_runs(const string &s){
        int n=s.size();
        vi hsh(n), pw(n);
        hsh[0]=s[0], pw[0]=1;
        rep(i,1,n-1){
            hsh[i]=(hsh[i-1]*base+s[i])%P;
            pw[i]=pw[i-1]*base%P;
        }
        auto val=[&](int l,int r){
            if(l==0){
                return hsh[r];
            }
            int res=( hsh[r]-hsh[l-1]*pw[r-l+1] )%P;
            if(res<0){
                res+= P;
            }
            return res;
        };
        auto lcp=[&](int i,int j){
            int l=0, r=n-max(i,j);
            while(l<r){
                int mid=(l+r+1)/2;
                if(val(i,i+mid-1)==val(j,j+mid-1)){
                    l=mid;
                }
                else{
                    r=mid-1;
                }
            }
            return l;
        };
        auto lcs=[&](int i,int j){
            int l=0, r=max(i,j)+1;
            while(l<r){
                int mid=(l+r+1)/2;
                if(val(i-mid+1,i)==val(j-mid+1,j)){
                    l=mid;
                }
                else{
                    r=mid-1;
                }
            };
            return l;
        };
        auto cmp=[&](int i,int j){
            int lc=lcp(i,j);
            return (i+lc==n? 0: s[i+lc])<(j+lc==n? 0: s[j+lc]);
        };
        vector< array<int,3> > res;
        auto chk=[&](int i,int j){
            if(s[i]==s[j]){
                int lc0=lcp(i,j), lc1=lcs(i,j)-1;
                if(lc0+lc1>=j-i){
                    res.pb({i-lc1,j+lc0-1,j-i});
                }
            }
        };
        vi stk;
        per(i,n-1,0){
            while(!stk.empty() && cmp(i, stk.back())){
                stk.pop_back();
            }
            if(!stk.empty()){
                chk(i, stk.back());
            }
            stk.pb(i);
        }
        stk.clear();
        per(i,n-1,0){
            while(!stk.empty() && cmp(stk.back(), i)){
                stk.pop_back();
            }
            if(!stk.empty()){
                chk(i, stk.back());
            }
            stk.pb(i);
        }
        return res;
    }
}
using RUNS::get_runs;

namespace hashtable{
    const int N=1e7, P=1e7+19;
    struct Set{
        int key[N], bg[P], nxt[N], tot;
        void clear(){
            rep(i,1,tot){
                bg[key[i]%P]=0;
            }
            tot=0;
        }
        bool count(int x){
            for(int id=bg[x%P]; id; id=nxt[id]){
                if(key[id]==x){
                    return 1;
                }
            }
            return 0;
        }
        void ins(int x){
            if(!count(x)){
                tot++;
                key[tot]=x, nxt[tot]=bg[x%P];
                bg[x%P]=tot;
            }
        }
    };
}
using hashtable::Set;
Set S;

namespace sam{
    const int N=2e5+5, M=N*2;
    array<int,26> s[M];
    int fa[M], len[M], tot;
    void init(){
        rep(i,0,tot){
            s[i].fill(0);
            fa[i]=0;
            len[i]=0;
        }
        tot=1;
    }
    int ins(int p,int c){
        int u=++tot;
        len[u]=len[p]+1;
        for(; p && !s[p][c]; p=fa[p]){
            s[p][c]=u;
        }
        if(p==0){
            fa[u]=1;
        }
        else{
            int v=s[p][c];
            if(len[v]==len[p]+1){
                fa[u]=v;
            }
            else{
                int t=++tot;
                s[t]=s[v], fa[t]=fa[v], len[t]=len[p]+1;
                fa[u]=fa[v]=t;
                for(; p && s[p][c]==v; p=fa[p]){
                    s[p][c]=t;
                }
            }
        }
        return u;
    }
    int countall(const string &s){
        init();
        int lst=1;
        for(char c:s){
            lst=ins(lst, c-'a');
        }
        int res=0;
        rep(i,2,tot){
            res+= len[i]-len[fa[i]];
        }
        return res;
    }
}

typedef __int128 ll;
const int P=1e18L+3, base=36634229;
void solve(){
    string s; cin>>s;
    int n=s.size();
    vi hsh(n), pw(n);
    hsh[0]=s[0], pw[0]=1;
    rep(i,1,n-1){
        hsh[i]=((ll)hsh[i-1]*base+s[i])%P;
        pw[i]=(ll)pw[i-1]*base%P;
    }
    auto val=[&](int l,int r){
        if(l==0){
            return hsh[r];
        }
        int res=(hsh[r]-(ll)hsh[l-1]*pw[r-l+1])%P;
        if(res<0){
            res+=P;
        }
        return (int)res;
    };
    int ans=sam::countall(s);
    vector< array<int,3> > run=get_runs(s);
    S.clear();
    for(auto x:run){
        rep(y, x[0], x[0]+x[2]-1){
            for(int z=y+x[2]*2-1; z<=x[1]; z+=x[2]){
                S.ins(val(y-1,z-1));
            }
        }
    }
    ans-= S.tot;
    cout<< ans <<'\n';
}
signed main(){
    #ifndef ONLINE_JUDGE
    assert(freopen(".in","r",stdin));
    #endif
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    int t; cin>>t;
    while(t--){
        solve();
    }
}