#include <bits/stdc++.h>
#define pii pair<int,int>
#define int long long
#define ff first
#define ss second
using namespace std;
const int mod = 1e9 + 7;
const int p1 = 97;
const int p2 = 107;
const int binv = 268041239;
const int binv2 = 224299067;
const int maxn = 1e6;
vector<int> pows(maxn+7,1);
vector<int> invs(maxn+7,1);
vector<int> pows2(maxn+7,1);
vector<int> invs2(maxn+7,1);
void init()
{
for (int i = 1; i < maxn; i++)
pows[i] = pows[i-1]*p1%mod;
for (int i = 1; i < maxn; i++)
invs[i] = invs[i-1]*binv%mod;
for (int i = 1; i < maxn; i++)
pows2[i] = pows2[i-1]*p2%mod;
for (int i = 1; i < maxn; i++)
invs2[i] = invs2[i-1]*binv2%mod;
}
void solve()
{
string s;
cin >> s;
int n = s.length();
vector<int> dp(n/2+2,0);
int back = n-1;
vector<int> hash(n);
hash[0] = s[0]*pows[0]%mod;
for (int i = 1; i < n; i++)
{
hash[i] = hash[i-1] + (s[i]*pows[i]%mod);
hash[i] %= mod;
}
vector<int> hash2(n);
hash2[0] = s[0]*pows2[0]%mod;
for (int i = 1; i < n; i++)
{
hash2[i] = hash2[i-1] + (s[i]*pows2[i]%mod);
hash2[i] %= mod;
}
auto mile = [&](int i,int j)
{
pii base = {hash[j],hash2[j]};
if (i > 0)
{
base.ff-=hash[i-1]-2*mod;
base.ss-=hash2[i-1]-2*mod;
base.ff%=mod;
base.ss%=mod;
base.ff*=invs[i];
base.ss*=invs2[i];
base.ff%=mod;
base.ss%=mod;
}
return ((pii)base);
};
int lst = 0;
for (int i = 0; i < n/2+1; i++)
{
if (i >= back)
break;
//cout << s.substr(j,i-j+1) << ' ' << s.substr(back,i-j+1) << " i: " << i << " j: " << j << '\n';
pii alpha = mile(lst,i);
pii sigma = mile(back,back+(i-lst));
if (alpha == sigma)
{
if (lst==0)
dp[i] = max(dp[i],2ll);
else if (dp[lst-1] > 0)
dp[i] = max(dp[i],dp[lst-1]+2);
lst = i+1;
}
back--;
}
int ans = 1;
if (n%2)
{
for (int i = 0; i < n/2+1; i++)
{
ans = max(ans,dp[i]+1);
}
}
else
{
for (int i = 0; i < n/2-1; i++)
{
ans = max(ans,dp[i]+1);
}
ans = max(ans,dp[n/2-1]);
}
cout << ans << '\n';
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
init();
while(t--)
{
solve();
}
return 0;
}
