#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=

NQp3ZXdld2UKcGVsYXRuYXMKa2VkdWEKZGkKam9namE=

5
wewewe
pelatnas
kedua
di
jogja