#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 5*1e5+5, INF = 1e9+9, mod = 1e9+9, base = 101;
int N = 2e6;
vector<ll> bp(N+1, 1);
void calc(){
for(int i = 1; i <= N; i++){
bp[i] = bp[i-1]*base%mod;
}
}
void solve(){
string s;
cin >> s;
int n = s.size();
s = ' ' + s;
vector<ll> hsh(n+1, 0);
for(int i = 1; i <= n; i++){
hsh[i] = hsh[i-1]+(s[i]-'a'+1)*bp[i-1];
}
auto get_hash = [&](int l, int r) -> ll{
ll raw = (hsh[r]-hsh[l-1]+mod)%mod;
return raw*bp[N-l]%mod;
};
vector<int> f(n+1, -INF);
f[0] = 0;
int ans = 1;
for(int i = 1; i <= n/2; i++){
for(int r = 1; r <= i; r++){
if(get_hash(i-r+1, i) == get_hash(n-i+1, n-(i-r+1)+1)){
f[i] = max(f[i], f[i-r]+2);
}
}
if(i == n/2 && n%2==0){
ans = max(ans, f[i]);
}else{
ans = max(ans, f[i]+1);
}
}
cout << ans;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
calc();
int t;
cin >> t;
while(t--){
solve();
cout << "\n";
}
return 0;
}
