#include "bits/stdc++.h"
using namespace std;
void solve(){
string s;
cin >> s;
int n = s.size();
int dp[n + 1][n + 1];
for(int i = 0;i < n + 1;i++){
for(int j = i;j < n + 1;j++){
dp[i][j] = 1;
}
for(int j = 0;j < i;j++){
dp[i][j] = 0;
}
}
for(int l = n - 1;l >= 0;l--){
for(int r = l;r <= n - 1;r++){
string suff = "";
string pref = "";
int nl = l,nr = r;
while(nl < nr){
pref += s[nl];
suff = s[nr] + suff;
if(pref == suff){
dp[l][r] = max(dp[l][r],dp[nl + 1][nr - 1] + 2) ;
}
nl++;
nr--;
}
}
}
cout << dp[0][n - 1] << "\n";
}
//(h[i] - h[j]) * (h[i] - h[j]) + pref[i] - pref[j + 1]
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int t = 1;
cin >> t;
while(t--){
solve();
}
}
