#include <iostream>
#include <cstring>
using namespace std;
 
char s[1001];
int length;
int ans[1000][1000];
 
void initialize(){
    memset(ans,0,sizeof(ans));
    for(int i = 0; i < length-1; i++){
        if(s[i] == s[i+1]){
            ans[i][i+1] = 2;
        }
    }
 
    for(int i = 0; i < length-2; i++){
        int val = (s[i] == s[i+1]) + (s[i+1] == s[i+2]) + (s[i] == s[i+2]);
        if( val == 3){
            ans[i][i+2] = 2;
        }
        else if(val == 1){
            ans[i][i+2] = 1;
        }
    }
}
 
void solve(){
    for(int i = 0; i < length-3; i++){
        ans[i][i+3] = ans[i][i+1] + ans[i+2][i+3];
    }
    for(int len = 5; len <= length; len++){
        for(int i = 0; i <= length-len; i++){
            int j = i + len-1;
            ans[i][j] = max(max(ans[i][i+1]+ans[i+2][j],ans[i][i+2]+ans[i+3][j]),max(ans[i][j-2]+ans[j-1][j],ans[i][j-3]+ans[j-2][j]));
        }
    }
}
 
int main(){
	int t;
	cin >> t;
	while(t--){
    		cin >> s;
    		length = strlen(s);
    		initialize();
    		solve();
    		cout << ans[0][length-1] << endl;
	}
}
 

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Y3N0cmluZz4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmNoYXIgc1sxMDAxXTsKaW50IGxlbmd0aDsKaW50IGFuc1sxMDAwXVsxMDAwXTsKCnZvaWQgaW5pdGlhbGl6ZSgpewogICAgbWVtc2V0KGFucywwLHNpemVvZihhbnMpKTsKICAgIGZvcihpbnQgaSA9IDA7IGkgPCBsZW5ndGgtMTsgaSsrKXsKICAgICAgICBpZihzW2ldID09IHNbaSsxXSl7CiAgICAgICAgICAgIGFuc1tpXVtpKzFdID0gMjsKICAgICAgICB9CiAgICB9CgogICAgZm9yKGludCBpID0gMDsgaSA8IGxlbmd0aC0yOyBpKyspewogICAgICAgIGludCB2YWwgPSAoc1tpXSA9PSBzW2krMV0pICsgKHNbaSsxXSA9PSBzW2krMl0pICsgKHNbaV0gPT0gc1tpKzJdKTsKICAgICAgICBpZiggdmFsID09IDMpewogICAgICAgICAgICBhbnNbaV1baSsyXSA9IDI7CiAgICAgICAgfQogICAgICAgIGVsc2UgaWYodmFsID09IDEpewogICAgICAgICAgICBhbnNbaV1baSsyXSA9IDE7CiAgICAgICAgfQogICAgfQp9Cgp2b2lkIHNvbHZlKCl7CiAgICBmb3IoaW50IGkgPSAwOyBpIDwgbGVuZ3RoLTM7IGkrKyl7CiAgICAgICAgYW5zW2ldW2krM10gPSBhbnNbaV1baSsxXSArIGFuc1tpKzJdW2krM107CiAgICB9CiAgICBmb3IoaW50IGxlbiA9IDU7IGxlbiA8PSBsZW5ndGg7IGxlbisrKXsKICAgICAgICBmb3IoaW50IGkgPSAwOyBpIDw9IGxlbmd0aC1sZW47IGkrKyl7CiAgICAgICAgICAgIGludCBqID0gaSArIGxlbi0xOwogICAgICAgICAgICBhbnNbaV1bal0gPSBtYXgobWF4KGFuc1tpXVtpKzFdK2Fuc1tpKzJdW2pdLGFuc1tpXVtpKzJdK2Fuc1tpKzNdW2pdKSxtYXgoYW5zW2ldW2otMl0rYW5zW2otMV1bal0sYW5zW2ldW2otM10rYW5zW2otMl1bal0pKTsKICAgICAgICB9CiAgICB9Cn0KCmludCBtYWluKCl7CglpbnQgdDsKCWNpbiA+PiB0OwoJd2hpbGUodC0tKXsKICAgIAkJY2luID4+IHM7CiAgICAJCWxlbmd0aCA9IHN0cmxlbihzKTsKICAgIAkJaW5pdGlhbGl6ZSgpOwogICAgCQlzb2x2ZSgpOwogICAgCQljb3V0IDw8IGFuc1swXVtsZW5ndGgtMV0gPDwgZW5kbDsKCX0KfQo=

MTcKMTIzMTIzMTIzCjc3Nzc3NzcKMzMzMzQKMzM0MzMKMzM0NDMzCjM0MzQzNAoyMzQ0MzIKNTQ1NDU1NDQ1NTQ0NTU0NDQ0NDU1NTU1NTQ0CjEyMzMyMzIzMjIyMzMyMjMzMzIyMjMKMTIzMTIzMTIxMjMyMjMyMjIzMjMyMzM0MzIxCjMzMjMyMjIzMjMyMgoyMjIyCjIzMQoyMjIyCjIyMwoyMgozMTIx

17
123123123
7777777
33334
33433
334433
343434
234432
545455445544554444455555544
1233232322233223332223
123123121232232223232334321
332322232322
2222
231
2222
223
22
3121