#include "bits/stdc++.h"
using namespace std;
#define int long long
const int MAXN = 3e5 + 10;
const int MOD = 1e9 + 7;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
int bm(int b, int p) {
if(p==0) return 1 % MOD;
int r = bm(b, p >> 1);
if(p&1) return (((r*r) % MOD) * b) % MOD;
return (r*r) % MOD;
}
int inv(int b) {
return bm(b, MOD-2);
}
int fastlog(int x) {
return (x == 0 ? -1 : 64 - __builtin_clzll(x) - 1);
}
void printcase(int i) { cout << "Case #" << i << ": "; }
struct palindromic_automaton {
vector<vector<int> >pam;
vector<vector<int> >revfail;
vector<int> oddrt,evenrt,fail,len,alleq,corr;
vector<int> cnt;
vector<int> dif,slink;
string s;//the string itself
// Declare other variables here
void init(int n) {
pam.resize(n + 5);
revfail.resize(n + 5);
fail.resize(n + 5);
len.resize(n + 5);
alleq.resize(n + 5);
corr.resize(n + 5);
cnt.resize(n + 5);
dif.resize(n + 5);
slink.resize(n + 5);
// Initialize other arrays here
}
void append(char c) {
int i = s.size();
s += c;
if(i == 0) {
fail[0] = -1;
len[0] = 1;
alleq[0] = 1;
corr[0] = 0;
cnt[0] = 1;
dif[0] = 0;
slink[0] = -1;
oddrt.push_back(0);
return;
}
int nxt=corr[i-1];
while(nxt!=-1){
if(alleq[nxt] && s[i]==s[i-1]) {
bool done=0;
for(int x:revfail[nxt]){
if(s[x]==s[i] && len[x]==len[nxt]+1){
corr[i]=x;
cnt[x]++;
done = 1;
break;
}
}
if(done) break;
fail[i]=nxt;
revfail[nxt].push_back(i);
len[i]=len[nxt]+1;
alleq[i]=1;
corr[i]=i;
cnt[i]=1;
break;
}
if(i-len[nxt]-1>=0 && s[i]==s[i-len[nxt]-1]) {
bool done=0;
for(int x:pam[nxt]){
if(s[x]==s[i]){
done=1;
corr[i]=x;
cnt[x]++;
break;
}
}
if(done)break;
pam[nxt].push_back(i);
corr[i]=i;
cnt[i]=1;
len[i]=len[nxt]+2;
alleq[i]=alleq[nxt]&(s[i]==s[i-1]);
int again=nxt;
fail[i]=-1;
while(fail[again]!=-1){
again=fail[again];
if(i-len[again]-1>=0 && s[i-len[again]-1]==s[i]){
for(int x:pam[again]){
if(s[x]==s[i]&&len[x]==len[again]+2){
fail[i]=x;
revfail[x].push_back(i);
break;
}
}
break;
}
if(alleq[again] && s[i]==s[i-1]){
for(int x:revfail[again]){
if(s[x]==s[i]&&len[x]==len[again]+1){
fail[i]=x;
revfail[x].push_back(i);
break;
}
}
break;
}
}
if(fail[i]==-1){
for(int x:oddrt){
if(s[x]==s[i]){
fail[i]=x;
revfail[x].push_back(i);
break;
}
}
}
break;
}
else nxt=fail[nxt];
}
if(nxt==-1){//single character
bool done=0;
for(int x: oddrt){
if(s[x]==s[i]){
corr[i]=x;
cnt[x]++;
done= 1;break;
}
}
if(!done) {
fail[i] = -1;
len[i] = 1;
alleq[i] = 1;
corr[i] = i;
cnt[i] = 1;
oddrt.push_back(i);
}
}
if(len[i] == 2) evenrt.push_back(i);
dif[i] = len[i] - (fail[i] == -1 ? 0 : len[fail[i]]);
if(fail[i] == -1 || dif[i] != dif[fail[i]]) slink[i] = fail[i];
else slink[i] = slink[fail[i]];
}
public:
};
void solve(int tc) {
string s;
cin >> s;
int n = s.size();
int l = 0, r = n - 1;
int dp[n], g[n];
for(int i=0; i<n; i++) dp[i] = g[i] = 0;
palindromic_automaton t;
t.init(n);
for(int i=0; i<n; i++) {
if(i % 2 == 0) t.append(s[l++]);
else t.append(s[r--]);
dp[i]=-1e9;
for(int x=t.corr[i];x>0;x=t.slink[x]) {
if(i-(t.slink[x]==-1?0:t.len[t.slink[x]])-t.dif[x] >= 0) {
g[x]=dp[i-(t.slink[x]==-1?0:t.len[t.slink[x]])-t.dif[x]];
}
else if(i-(t.slink[x]==-1?0:t.len[t.slink[x]])-t.dif[x] == -1) {
g[x]=0;
}
if(t.dif[x]==t.dif[t.fail[x]]) g[x]=max(g[x],g[t.fail[x]]);
if(i%2 == 1) dp[i] = max(dp[i], g[x] + 1);
}
}
int ans = dp[n-1] * 2;
for(int i=0; i+1<n; i++) ans = max(ans, dp[i] * 2 + 1);
ans = max(ans, 1ll);
cout << ans << "\n";
}
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
int t = 1; cin >> t;
for(int i=1; i<=t; i++) solve(i);
}
// 勿忘初衷
