#include<bits/stdc++.h>
using namespace std;
        string s;
bool judge(int l,int r){ 
	int flag=1;
	while(l<r){
		if(s[l]==s[r]){
			l++,r--;
		}
		else {
			flag=0;
			break;
		}
	}
	
	
	if(flag)return 1;
	
	return 0;
	
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {

        int dp[1005];
        dp[0]=1;
        cin>>s;
        int n=s.size();
        for(int i=1;i<n;i++)
        {
            dp[i]=dp[i-1]+1;
            for(int j=0;j<=i;j++)
                if(judge(j,i))
                    dp[i]=min(dp[i],dp[j-1]+1);
        }
        cout<<dp[n-1]<<endl;
    }
    return 0;
}