#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int T;
cin >> T;
for (int Ti = 0; Ti < T; ++Ti) {
string w;
cin >> w;
int n = w.size();
int dp[n][n] {};
for (int s = 2; s <= n; s += 2) {
for (int i = 0; i+s <= n; ++i) {
int j = i+s-1;
if (w[i] != w[j]) dp[i][j] = s == 2 || dp[i+1][j-1];
for (int k = 2; k <= s-2; k += 2) {
dp[i][j] |= dp[i][i+k-1] && dp[i+k][j];
}
}
}
int dp2[n];
for (int i = 0; i < n; ++i) {
dp2[i] = 0;
if (i) dp2[i] = dp2[i-1];
for (int s = 2; s <= i+1; s += 2) {
if (dp[i-s+1][i]) {
if (s == i+1) dp2[i] = s;
else dp2[i] = max(dp2[i], s+dp2[i-s]);
}
}
}
cout << dp2[n-1] << endl;
}
}
