/* * Author:  Bingo * Created Time:  2015/1/25 23:49:49 * File Name: uva11584.cpp */#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <algorithm>#include <string>#include <vector>#include <stack>#include <queue>#include <set>#include <time.h>using namespace std;const int maxint = -1u>>1;const int maxlen=1050;int d[maxlen];int s[maxlen][maxlen];string st;int work(){    int len=st.size();    memset(s,0,sizeof(s));    for (int i=0;i<len;i++){        int p,q;        s[i][i]=1;        //ji        p=i-1;q=i+1;        while (p>=0&&q<len&&st[p]==st[q]){            s[p][q]=1;            p--;q++;        }        //odd_left        p=i-1;q=i;        while (p>=0&&q<len&&st[p]==st[q]){            s[p][q]=1;            p--;q++;        }        //odd_right        p=i;q=i+1;        while (p>=0&&q<len&&st[p]==st[q]){            s[p][q]=1;            p--;q++;        }    }}//s[i][j]是否为回文串int main(){    int T;    cin>>T;    //string st;    while (T--){        cin>>st;        work();        int len=st.size();        for (int i=0;i<len;i++)            d[i]=100000;        for (int i=0;i<len;i++){            int j=0;            if (s[0][i]) d[i]=1;            else            for (j=0;j<i;j++){                if (s[j+1][i]) d[i]=min(d[i],d[j]+1);            }        }        cout<<d[len-1]<<endl;    }    return 0;}