#include <stdio.h>

 #include <string.h>

 #include <algorithm>

 using namespace std;

 char a[];

 int C(int x,int y)

 {

     int flg=;

     while(x<y)

     {

         if(a[x]!=a[y])

         {

             flg=;

             break;

         }

         x++,y--;

     }

     return flg;

 }

 int main()

 {

     int T;

     int dp[];

     scanf("%d",&T);

     while(T--)

     {

         int n,i,j;

         scanf("%s",a);

         memset(dp,,sizeof(dp));

         n=strlen(a);

         dp[]=;

         for(i=;i<n;i++)

         {

             dp[i]=dp[i-]+;

             for(j=i-;j>;j--)

             {

                 if(C(j,i))

                 {

                     dp[i]=min(dp[i],dp[j-]+);

                 }

             }

             if(C(,i))

                 dp[i]=;

         }

         /*for(i=0;i<n;i++)

             printf("%d ",dp[i]);

         printf("\n");*/

         printf("%d\n",dp[n-]);

     }

     return ;

 }