#include <iostream>

#include <algorithm>

#include <cstring>

#include<cstdio>

using namespace std;

const int MAX = ;

int len, p[*MAX];

char str[MAX], newstr[*MAX];

bool isPal[MAX][MAX];

void change()

{

     int i;

     newstr[] = '@';

     newstr[] = '#';

     for (i = ; i < len; i++){

         newstr[*i + ] = str[i];

         newstr[*i + ] = '#';

     }

     newstr[*len + ] = '\0';

     return ;

}

#define toPre(x) ((x-1)>>1)

void Manacher()

{

    int i, j, id, maxid = ;

    len =  * len + ;

    for (i = ; i < len; i++){

        if (maxid > i){

            p[i] = min(p[*id - i], maxid - i);//利用对称性快速计算p数组

        }

        else{

            p[i] = ;

        }

        while (newstr[i+p[i]] == newstr[i-p[i]])

            p[i]++;

        if (p[i] + i > maxid){

            maxid = p[i] + i;

            id = i;

        }

    }

    for( i = ; i < len; i++){

        char pivot = newstr[i];

        p[i]--;

        for(j = !(pivot<='z'&&pivot>='a'); j < p[i]; j+=){

            int u = toPre(i-j),v = toPre(i+j);

            isPal[u][v] = true;

        }

    }

}

int d[MAX];

int main()

{

    //freopen("in.txt","r",stdin);

    int T; scanf("%d",&T);

    while (T--){

        scanf("%s",str);

        len = strlen(str);

        change();

        memset(isPal,,sizeof(isPal));

        Manacher();

        len = (len-)>>;

        for(int i = ; i < len; i++){

            d[i] = isPal[][i]?:i+;

            for(int j = ; j < i; j++)if(isPal[j+][i]){

                d[i] = min(d[i],d[j]+);

            }

        }

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

    }

   // system("pause");

   return ;

}