#include <iostream>#include <string.h>#include <string>#define N 1002using namespace std;int f[N];bool d[N][N];/*    如果(i,j)回文(i<=j)，那么最小长度一定等于f[j+1]+1    用动态规划解决回文串的判断节省时间，牺牲空间 */ int main(){//    freopen("D:/Documents/work/in.txt", "r", stdin);    int n, t, i, j, result;    cin>>t;    while(t--)    {        string s;        cin>>s;        n=s.length();        memset(f, 1000000, sizeof(f));        memset(d, false, sizeof(d));        for (int i = 0; i <= n; i++)            f[i] = n-i;        for (int i = n - 1; i >= 0; i--) {            for (int j = i; j < n; j++) {                if (s[i] == s[j] && (j-i<2 || d[i+1][j-1])) {                    d[i][j] = true;                    f[i] = min(f[i], f[j+1]+1);                }            }        }        cout<<f[0]<<endl;    }     return 0;}