Stuff

#include <stdio.h>
#include <string.h>
#define INF 1000000000

int len;
int d[1005][1005];
char s[1005];

int mini( int a, int b ){
    return a<b?a:b;
}

int dp( int x, int y ){
    if(d[x][y]!=INF) return d[x][y];
    if(x>y)return INF;
    else if(y==x+1){
        if(s[x]==s[y])d[x][y] = 1;
        else d[x][y] = 2;
        return d[x][y];
    }

    for( int i=y; i>=x; i-- ){
        if(s[x]==s[i]){
            if( i<y ){
                d[x][y] = mini( d[x][y],dp(x,i) + dp(i+1,y) );
                if(d[x][y]==2)break;
            }
            else{
                int ret = dp(x+1,y-1);
                if(ret!=1)ret+=2;

                d[x][y] = mini( d[x][y], ret);
                if(d[x][y]==1)break;
            }
        }
    }

    return d[x][y];
}

int main(){
    int t;
    scanf("%d",&t);

    while(t--){
        scanf("%s",s);

        len = strlen(s);

        for(int i=0;i<len;i++){
            for(int j=0;j<len;j++){
                d[i][j] = INF;
            }
            d[i][i] = 1;
        }

        printf("%d\n",dp(0,len-1));
    }

    return 0;
}