#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;

typedef unsigned long long ull;
const ull base=36634229;

namespace runs{ // code from: https://loj.ac/s/2043370
    const int N=2e5+5,B=131,mod=998244353;
    int n,tot,cnt,a[N],pw[N],hs[N],ly[2][N];
    char s[N];
    struct ss{int l,r,p;}xl[2*N],xl1[2*N];
    bool cmp(ss x,ss y){return (x.l==y.l?x.r<y.r:x.l<y.l);}
    int js(int x,int y,int z){return (hs[x+z-1]-hs[y+z-1]+(hs[y-1]-hs[x-1])*pw[z])%mod;}
    int lcp(int l,int r){
        int le=0,ri=min(n-l+1,n-r+1);
        while(le<ri){
            int mid=(le+ri+1)/2;
            if(js(l,r,mid)==0) le=mid; else ri=mid-1;
        }return le;
    }
    int lcs(int l,int r){
        int le=0,ri=min(l,r);
        while(le<ri){
            int mid=(le+ri+1)/2;
            if(js(l-mid+1,r-mid+1,mid)==0) le=mid; else ri=mid-1;
        }return le;
    }
    void sol(int opt){
        stack<int> st;
        per(i,n,1){
            while(st.size()){
                int dq=lcp(st.top(),i);
                if(a[st.top()+dq]>a[i+dq]) st.pop(); else break;
            }ly[opt][i]=(st.size()?st.top()-1:n),st.push(i);
            int dl=i,dr=ly[opt][i],d2=dr+lcp(dl,dr+1),d1=dl-lcs(dl-1,dr);
            if(d2-d1+1>=2*(dr-dl+1)) xl[++tot]={d1,d2,dr-dl+1};
        }
    }
    vector< array<int,3> > work(const string &_s){
        n=0, tot=0, cnt=0;
        memset(a, 0, sizeof(a));
        memset(pw, 0, sizeof(pw));
        memset(hs, 0 ,sizeof(hs));
        memset(ly, 0, sizeof(ly));
        memset(s, 0, sizeof(s));
        memset(xl, 0, sizeof(xl));
        memset(xl1, 0, sizeof(xl1));
        rep(i,0,(int)_s.size()-1){
            s[i+1]=_s[i];
        }
        n=strlen(s+1),pw[0]=1;
        rep(i,1,n) a[i]=s[i]-'a'+1,pw[i]=pw[i-1]*B%mod,hs[i]=(hs[i-1]*B+a[i])%mod;
        sol(0); rep(i,1,n) a[i]=27-a[i]; sol(1);
        sort(xl+1,xl+tot+1,cmp);
        rep(i,1,tot) if(i==1||xl[i].l!=xl[i-1].l||xl[i].r!=xl[i-1].r) xl1[++cnt]=xl[i];
        
        vector< array<int,3> > res(cnt);
        rep(i,0,cnt-1){
            res[i]={xl1[i+1].l, xl1[i+1].r, xl1[i+1].p};
        }
        return res;
    }
}

namespace hashtable{
    const int N=1e7, P=1e7+19;
    struct Set{
        ull key[N];
        int bg[P], nxt[N], tot;
        void clear(){
            rep(i,1,tot){
                bg[key[i]%P]=0;
            }
            tot=0;
        }
        bool count(ull x){
            for(int id=bg[x%P]; id; id=nxt[id]){
                if(key[id]==x){
                    return 1;
                }
            }
            return 0;
        }
        void ins(ull 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;
    }
}

void solve(){
    string s; cin>>s;
    int n=s.size();
    vector<ull> hsh(n), pw(n);
    hsh[0]=s[0], pw[0]=1;
    rep(i,1,n-1){
        hsh[i]=hsh[i-1]*base+s[i];
        pw[i]=pw[i-1]*base;
    }
    auto val=[&](int l,int r){
        if(l==0){
            return hsh[r];
        }
        return hsh[r]-hsh[l-1]*pw[r-l+1];
    };
    int ans=sam::countall(s);
    vector< array<int,3> > run=runs::work(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();
    }
}