#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
scanf("%d", &n);
while (n--) {
string s;
cin >> s;
int len = s.length();
int dp[len][len];
for (int i = 0; i < len; i++) {
dp[i][i] = 1;
}
for (int i = len-1; i >= 0; i--) {
for (int j = i+1; j < len; j++) {
if (s[i] == s[j]) {
dp[i][j] = 2;
if (j - i > 1) {
dp[i][j] += dp[i+1][j-1];
}
} else {
dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
}
}
}
cout << dp[0][len-1] << '\n';
}
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IG1haW4oKSB7CglpbnQgbjsKCXNjYW5mKCIlZCIsICZuKTsKCXdoaWxlIChuLS0pIHsKCQlzdHJpbmcgczsKCQljaW4gPj4gczsKCQlpbnQgbGVuID0gcy5sZW5ndGgoKTsKCQlpbnQgZHBbbGVuXVtsZW5dOwoJCWZvciAoaW50IGkgPSAwOyBpIDwgbGVuOyBpKyspIHsKCQkJZHBbaV1baV0gPSAxOwoJCX0KCQlmb3IgKGludCBpID0gbGVuLTE7IGkgPj0gMDsgaS0tKSB7CgkJCWZvciAoaW50IGogPSBpKzE7IGogPCBsZW47IGorKykgewoJCQkJaWYgKHNbaV0gPT0gc1tqXSkgewoJCQkJCWRwW2ldW2pdID0gMjsKCQkJCQlpZiAoaiAtIGkgPiAxKSB7CgkJCQkJCWRwW2ldW2pdICs9IGRwW2krMV1bai0xXTsKCQkJCQl9CgkJCQl9IGVsc2UgewoJCQkJCWRwW2ldW2pdID0gbWF4KGRwW2krMV1bal0sIGRwW2ldW2otMV0pOwoJCQkJfQoJCQl9CgkJfQoJCWNvdXQgPDwgZHBbMF1bbGVuLTFdIDw8ICdcbic7Cgl9Cn0=