#include <bits/stdc++.h>
using namespace std;
#define int long long
int const N=10005;
int const mod=1e9+7;
int const base=727;
int dp[N];
int Hash[N];
int pw[N];
void pre(){
pw[0]=1;
for(int i=1;i<N;i++)
pw[i]=(pw[i-1]*base)%mod;
}
int make_hash(int l,int r){
l--;
int h=((Hash[r]-((Hash[l]*pw[r-l])%mod))+mod)%mod;
return h;
}
void solve(){
string s;
cin>>s;
int n=s.length();
int hsh=0;
for(int i=0;i<n;i++){
hsh*=base;
hsh%=mod;
hsh+=s[i];
hsh%=mod;
Hash[i+1]=hsh;
}
for(int i=0;i<=n;i++)
dp[i]=0;
int ans=0;
for(int i=1;i<=(n/2);i++){
dp[i]=-1;
for(int j=0;j<i;j++)
if(make_hash(j+1,i)==make_hash(n-(i-1),n-(j))&& dp[j]>-1)
dp[i]=max(dp[i],dp[j]+2);
// cout<<dp[i]<<endl;
ans=max(ans,dp[i]+(i*2<n));
}
cout<<max(1LL,ans)<<endl;
}
signed main(){
pre();
int t;
cin>>t;
while(t--)
solve();
return 0;
}
