#include<bits/stdc++.h>
#pragma GCC optimize("O2")
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define all(c) c.begin(), c.end()
#define endl "\n"
#define sz(u) (int)(u.size())
#define L(x)(2*x)
#define R(x)(2*x+1)
#define M(x,y)((x+y)/2)
#define int long long
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int p=256,md=1e9+7;
const int N=1e6;
vector<int> pw(N),pref;
void precalc(){
pw[0]=1;
for(int i=1;i<N;i++)
pw[i]=(pw[i-1]*p)%md;
}
int bpow(int a,int k){
int ans=1;
while(k){
if(k&1)
ans=(ans*a)%md;
a=(a*a)%md;
k>>=1;
}
return ans;
}
int inv(int a){
return bpow(a,md-2);
}
int get_hash(int l,int r){
if(l==0)
return pref[r];
int ans=((pref[r]-pref[l-1])%md +md)%md;
ans=(ans*inv(pw[l]))%md;
return ans;
}
void solve(){
string s;
cin>>s;
int n=sz(s);
pref=vector<int>(n,0);
for(int i=0;i<n;i++){
if(i!=0)
pref[i]=pref[i-1];
pref[i]=(pref[i]+ ((ll)pw[i]*s[i])%md )%md;
}
vector<vector<int>> pos(26);
vector<int> cur(26,0);
for(int i=0;i<n;i++)
pos[s[i]-'a'].PB(i);
int ans=0,curl=0,curr=n-1;
while(1){
//cout<<curl<<" "<<curr<<endl;
int c=s[curr]-'a';
bool fnd=0;
for(int j=cur[c];j<sz(pos[c]);j++){
int i=pos[c][j];
if(i>=curl && curr+curl>2*i && get_hash(curl,i)==get_hash(curr+curl-i,curr)){
fnd=1;
ans+=2;
curr=curr+curl-i-1;
curl=i+1;
cur[c]=i+1;
break;
}
}
if(fnd){
if(curl==curr){
ans++;
break;
}
if(curl>curr)
break;
}
else{
ans++;
break;
}
}
cout<<ans;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
precalc();
int t;
cin>>t;
while(t--){
solve();
cout<<endl;
}
}
