代码：

#include<bits/stdc++.h>
using namespace std;

const int INF=(1<<30);

int t,len;
string s;
bool a[1001][1001];
int dpp[1001];

void init_pd()
{
    for(int i=0;i<len;i++)
    {
        int l,r;
        l=r=i;
        a[l][r]=true;
        if(s[l-1]!=s[r+1])r++;
        while(l>=0&&r<len&&s[l]==s[r])
        {
            a[l][r]=true;
            l--,r++;
        }
    }
    return;
}

int dp(int i)
{
    if(i==-1)return 0;
    int& ans=dpp[i];
    if(ans)return ans;
    ans=INF;
    for(int j=0;j<=i;j++)
    {
        if(a[j][i])ans=min(ans,dp(j-1)+1);
    }
    return ans;
}

int main()
{
    //freopen("cc.in","r",stdin);
    cin>>t;
    while(t--)
    {
        cin>>s;
        len=s.size();
        memset(a,false,sizeof(a));
        memset(dpp,0,sizeof(dpp));
        init_pd();
        if(t!=0)cout<<dp(len-1)<<endl;
        else cout<<dp(len-1);
    }

    return 0;
}