#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;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();
}
}