1 #include<cstdio>

 2 #include<cstdlib>

 3 #include<cstring>

 4 #include<iostream>

 5 using namespace std;

 6

 7 #define N 1010

 8 char s[N];

 9 int p[N][N],f[N];

10

11 int mmin(int x,int y) {return x<y?x:y;}

12

13 int main()

14 {

15     int T,l;

16     scanf("%d",&T);

17     while (T--)

18     {

19       scanf("%s",s+1);

20       l=strlen(s+1);

21       memset(p,0,sizeof(p));

22       for (int i=1;i<=l;i++)

23       {

24         int x=0;

25         while (i-x>0&&i+x<=l&&s[i-x]==s[i+x]) p[i-x][i+x]=1,x++;

26         x=1;

27         while (i-x>0&&i+x-1<=l&&s[i-x]==s[i+x-1]) p[i-x][i+x-1]=1,x++;

28       }

29       f[0]=-1;

30       for (int i=1;i<=l;i++)

31       {

32         f[i]=i-1;

33         for (int j=0;j<i;j++)

34           if (p[j+1][i]) f[i]=mmin(f[i],f[j]+1);

35       }

36       printf("%d\n",f[l]);

37     }

38     return 0;

39 }