#include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <algorithm>

 #include <vector>

 #include <string>

 #include <set>

 #include <map>

 #include <list>

 #include <unordered_set>

 #include <unordered_map>

 #include <cmath>

 #define FRER() freopen("in.txt", "r", stdin)

 #define FREW() freopen("out.txt", "w", stdout)

 #define INF 0x3f3f3f3f

 using namespace std;

 const int maxn =  + ;

 int n, len, l, r;

 char str[maxn];

 bool check[maxn][maxn];

 int dp[maxn];

 int main()

 {

     //FRER();

     scanf("%d", &n);

     while(n--) {

         scanf("%s", str);

         len = strlen(str);

         memset(check, , sizeof(check));

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

             l = r = i;

             while(l >=  && r < len) {

                 if(str[l] == str[r]) {

                     check[l + ][r + ] = ;

                     --l; ++r;

                 }

                 else break;

             }

             l = i;

             r = i + ;

             while(l >=  && r < len) {

                 if(str[l] == str[r]) {

                     check[l + ][r + ] = ;

                     --l; ++r;

                 }

                 else break;

             }

         }

         memset(dp, , sizeof(dp));

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

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

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

                 if(check[j][i])

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

             }

         }

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

     }

     return ;

 }