#define MAXN 1000+10

char str[MAXN];
int dp[MAXN];
int t;

bool isPalind(int l, int r)
{
    while(l<r)
    {
        if(str[l] != str[r]) return false;
        ++l;
        --r;
    }
    return true;
}

int main(int argc, char const *argv[])
{
    scanf("%d", &t);
    while(t--)
    {
        scanf("%s", str+1);
        int len = strlen(str+1);
        memset(dp, 0, sizeof(int)*len);
        for(int i=1; i<=len; ++i)
        {
            dp[i] = i+1;
            for(int j=1; j<=i; ++j)
            {
                if(isPalind(j, i))
                {
                    dp[i] = min(dp[i], dp[j-1]+1);
                }
            }
        }
        printf("%d\n", dp[len]);
    }
    return 0;
}