#include<stdio.h>
#include<stdlib.h>

int DP[1001][10001] = {0} ;

int pail(char str[1001], int left, int right)//檢查是否回文
{
if( right - left >= 2 )
{
     if( DP[left+1][right-1] == 1 && str[left] == str[right] )
          return 1 ;

      else
          return 0 ;
}
else if( str[left] == str[right] )
      return 1 ;

return 0 ;

}

int main()
{
int num, len = 0 ;
char str[1000] ;
scanf("%d",&num);
while(num > 0)
{
     scanf("%s",&str);
     for(int i = 0 ; str[i] != '\0' ; i++, len++)
          DP[i][i] = 1 ;

    for(int i = 1 ; i < len ; i++)
    {
         for(int j = 0 ; i+j < len ; j++)
         {
             if( pail(str,j,j+i) == 1 )
            {
                DP[j][j+i] = 1 ;
                continue ;
            }

           for(int sepr = 0 ; sepr < i ; sepr++)
          {
                if( DP[j][j+i] == 0 || DP[j][j+sepr] + DP[j+sepr+1][j+i] < DP[j][j+i] )
                    DP[j][j+i] = DP[j][j+sepr] + DP[j+sepr+1][j+i] ;

          }
       }
    }

printf("%d\n",DP[0][len-1]);
len = 0 ;
num--;
for(int i = 0 ; str[i] != '\0' ; i++)
{
     for(int j = 0 ; str[j] != '\0' ; j++ )
     DP[i][j] = 0 ;
}
}
}