#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=5e5+5;int n;
#pragma GCC optimize("Ofast")
namespace sgt2{
    struct SGT{
        int ls, rs, sum;
    }tr[25*N];
    #define ls(x) tr[x].ls
    #define rs(x) tr[x].rs
    #define sum(x) tr[x].sum
    // #define gcd(x) tr[x].gcd
    int cnt=0, rt[N];
    inline void push_up(int x){
        sum(x)=sum(ls(x))+sum(rs(x));
        // gcd(x)=__gcd(gcd(ls(x)), gcd(rs(x)));
    }
    bool insert(int &x, int l, int r, int k){
        if(!x) x=++cnt;
        if(l==r){
            int p=sum(x);
            sum(x)=1;
            return !p;
        }
        int mid=(l+r)/2;
        bool rt=(k<=mid?insert(ls(x), l, mid, k):insert(rs(x), mid+1, r, k));
        push_up(x);
        return rt;
    }
    void merge(int &x, int y, int l, int r){
        if(!x||!y){
            x=x|y;
            return;
        }
        if(l==r){
            return;
        }
        int mid=(l+r)/2;
        merge(ls(x), ls(y), l, mid);
        merge(rs(x), rs(y), mid+1, r);
        push_up(x);
    }
    int ask(int x, int l, int r, int L, int R){
        if(!x) return 0;
        if(L<=l&&r<=R){
            return sum(x);
        }
        int mid=(l+r)/2, res=0;
        if(L<=mid) res+=ask(ls(x), l, mid, L, R);
        if(R>mid) res+=ask(rs(x), mid+1, r, L, R);
        return res;
    }
    int ask(int x, int l, int r, int k){
        if(!x) return 0;
        if(l==r){
            return sum(x);
        }
        int mid=(l+r)/2;
        return k<=mid?ask(ls(x), l, mid, k):ask(rs(x), mid+1, r, k);
    }
    void print(int x, int l, int r){
        if(!x) return;
        if(l==r){
            cerr << l << ' ';
            return;
        }
        int mid=(l+r)/2;
        print(ls(x), l, mid);
        print(rs(x), mid+1, r);
    }
}
int dtmp[N];
int del[N], top;
void instmp(int x){
    if(!dtmp[x]){
        dtmp[x]=1;
        del[++top]=x;
    }
}
void clear(){
    for(int i=1; i<=top; ++i){
        dtmp[del[i]]=0;
    }
    top=0;
}
namespace sgt1{
    struct SGT{
        int ls, rs, mi, mx;
    }tr[20*N];
    #define ls(x) tr[x].ls
    #define rs(x) tr[x].rs
    #define mi(x) tr[x].mi
    #define mx(x) tr[x].mx
    int cnt=0;
    int rt[N];
    void push_up(int x){
        mi(x)=min(mi(ls(x)), mi(rs(x)));
        mx(x)=max(mx(ls(x)), mx(rs(x)));
    }
    void insert(int &x, int l, int r, int k){
        if(!x) x=++cnt;
        if(l==r){
            mi(x)=mx(x)=k;
            return;
        }
        int mid=(l+r)/2;
        k<=mid?insert(ls(x), l, mid, k):insert(rs(x), mid+1, r, k);
        push_up(x);
    }
    void merge(int &x, int y, int l, int r, int &L){
        if(!x&&!y) return;
        if(!x||!y){
            x=x|y;
            // cerr << L << ' ' << mi(x) << ' ' << mx(x) << '\n';
            if(L){
                instmp(mi(x)-L);
            }
            L=mx(x);
            return;
        }
        if(l==r){
            if(L){
                instmp(mi(x)-L);
            }
            L=mx(x);
            return;
        }
        int mid=(l+r)/2;
        merge(ls(x), ls(y), l, mid, L);
        merge(rs(x), rs(y), mid+1, r, L);
        push_up(x);
    }
    void print(int x, int l, int r){
        if(!x) return;
        if(l==r){
            cerr << l << ' ';
            return;
        }
        int mid=(l+r)/2;
        print(ls(x), l, mid);
        print(rs(x), mid+1, r);
    }
}

struct SAM{
    int t[26], f, len;
}a[N];
vector<int> e[N];
int tot, lst;
void init(){
    sgt1::mi(0)=1e9;
    for(int i=1; i<=sgt1::cnt; ++i){
        sgt1::ls(i)=sgt1::rs(i)=0;
        sgt1::mi(i)=1e9, sgt1::mx(i)=0;
    }sgt1::cnt=0;
    for(int i=1; i<=sgt2::cnt; ++i){
        sgt2::ls(i)=sgt2::rs(i)=0;
        sgt2::sum(i)=0; 
        // sgt2::gcd(i)=0;
    }sgt2::cnt=0;
    for(int i=1; i<=tot; ++i){
        memset(a[i].t, 0, sizeof(a[i].t));
        a[i].f=a[i].len=0;
        sgt1::rt[i]=0; sgt2::rt[i]=0;
        vector<int>().swap(e[i]);
    }
    tot=lst=1;
}
void ins(int c, int i){
    int p=lst, np=++tot; lst=np; sgt1::insert(sgt1::rt[np], 1, n, i);
    a[np].len=a[p].len+1;
    for(;p&&!a[p].t[c];p=a[p].f) a[p].t[c]=np;
    if(!p) a[np].f=1;
    else{
        int v=a[p].t[c];
        if(a[v].len==a[p].len+1){
            a[np].f=v;
        }else{
            int nv=++tot; a[nv]=a[v];
            a[nv].len=a[p].len+1;
            for(;p&&a[p].t[c]==v;p=a[p].f) a[p].t[c]=nv;
            a[np].f=a[v].f=nv;
        }
    }
}
ll ans;
int get2(int rot, int L, int R){
    if(L<=R) return sgt2::ask(rot, 1, n, L, R);
    return 0;
}
string s;
bool vis[N];
int pos[50*N], topp;
void dfs(int x){
    for(auto y:e[x]){
        dfs(y);
        sgt2::merge(sgt2::rt[x], sgt2::rt[y], 1, n);
    }
    for(auto y:e[x]){
        int L=0;
        sgt1::merge(sgt1::rt[x], sgt1::rt[y], 1, n, L);
    }
    sort(del+1, del+top+1);
    for(int i=1; i<=top; ++i){
        int p=del[i];
        if(!sgt2::ask(sgt2::rt[x], 1, n, p)){
            for(int j=p; j<=a[x].len; j+=p){
                // assert(!vis[j]);
                if(vis[j]) continue;
                if(j==80352+9){
                    cerr << j << '\n';
                    cerr << sgt2::rt[x] << ' ' << sgt2::cnt << '\n';
                }
                if(!sgt2::insert(sgt2::rt[x], 1, n, j)){
                    for(int k=j; k<=a[x].len; k+=j){
                        vis[k]=1;
                        pos[++topp]=k;
                    }
                }
            }
        }
    }
    for(int i=1; i<=topp; ++i){
        vis[pos[i]]=0;
    }
    topp=0;
    clear();
    // cerr << x << ": " << a[a[x].f].len+1 << " " << a[x].len << '\n';
    // sgt1::print(sgt1::rt[x], 1, n); cerr << '\n';
    // for(int i=1; i<=top; ++i){
    //     cerr << del[i] << ' ';
    // }
    // cerr << '\n';
    // sgt2::print(sgt2::rt[x], 1, n);
    // cerr << '\n';
    // int gcd=sgt2::askgcd(sgt2::rt[x], 1, n, 1, a[x].len-1);
    
    // if(f[x]<a[x].len&&gcd!=f[x]){
    //     
    //     for(int i=182-6+1; i<=182; ++i){
    //         cerr << s[i];
    //     }
    //     cerr << '\n';
    // }
    // assert(f[x]>=a[x].len||gcd==f[x]);
    
    ans+=a[x].len-a[a[x].f].len; 
    int tp=get2(sgt2::rt[x], a[a[x].f].len+1, a[x].len);
    ans-=tp;
    // cerr << "del: " << tp << '\n';
}
int main(){
    // cerr << (sizeof(sgt1::tr)+sizeof(sgt2::tr)+sizeof(a))/1024.0/1024 << '\n';
    // freopen("book.in", "r", stdin);
    // freopen("book.out", "w", stdout);
    // freopen("book.err", "w", stderr);
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while(T--){
        ans=0;
        // cin >> n >> s;
        cin >> s; n=s.length();
        s="#"+s; init();
        for(int i=1; i<=n; ++i){
            ins(s[i]-'a', i);
        }
        for(int i=2; i<=tot; ++i){
            e[a[i].f].push_back(i);
        }
        dfs(1);
        cout << ans << '\n';
        // return 0;
    }
    return 0;
}