#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
//#include "boxes.h"
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<61);
const int inf=(1<<30);
const int nmax=1e6+50;
const int mod=1e9+7;
using namespace std;
int n,i,j,rs,f[nmax],x,t;
ll p[]={31,67},m[]={1000003,1000000007},pw[2][nmax],in[2][nmax],hs[2][nmax];
string s;
ll bn(ll x,ll p,ll md)
{
ll rs=1;
while(p)
{
if(p&1LL)rs=(rs*x)%md;
x=(x*x)%md;
p>>=1LL;
}
return rs;
}
bool eq(int L,int R,int A,int B)
{
ll x[2][2];
int l[2],r[2];
l[0]=L,l[1]=A,r[0]=R,r[1]=B;
for(int i=0;i<2;i++)
{
for(int j=0;j<2;j++)
{
x[i][j]=hs[j][r[i]];
if(l[i])x[i][j]=(x[i][j]-hs[j][l[i]-1]+m[j])%m[j];
x[i][j]=(x[i][j]*in[j][l[i]])%m[j];
}
}
for(int i=0;i<2;i++)if(x[0][i]!=x[1][i])return 0;
return 1;
}
int main()
{
//freopen("sol.in","r",stdin);
//freopen("sol.out","w",stdout);
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
cin>>t;
while(t--)
{
cin>>s;
n=s.size();
for(i=0;i<n;i++)
{
if(i==0)
{
for(j=0;j<2;j++)
{
pw[j][i]=1;
hs[j][i]=s[i];
in[j][i]=1;
}
}
else
{
for(j=0;j<2;j++)
{
pw[j][i]=(pw[j][i-1]*p[j])%m[j];
hs[j][i]=(hs[j][i-1]+pw[j][i]*s[i])%m[j];
in[j][i]=bn(pw[j][i],m[j]-2,m[j]);
}
}
}
rs=1;
for(i=0;i<n/2;i++)
{
f[i]=-1;
for(j=i;j>=0;j--)
{
if(j && f[j-1]==-1)continue;
x=0;
if(j)x=f[j-1];
if(eq(j,i,n-i-1,n-j-1))
{
f[i]=max(f[i],x+2);
}
}
if(f[i]!=-1)
{
if(i==(n/2)-1 && n%2==0)rs=max(rs,f[i]);
else rs=max(rs,f[i]+1);
}
}
cout<<rs<<endl;
}
return 0;
}
