/*状态转移f[i]=min(f[i],f[j]+f[i^j]);

 就是j状态+i^j状态=i状态，f[i]记录的是从i删除1要的最小步数*/

 #include<string.h>

 #include<stdio.h>

 #include<algorithm>

 using namespace std;

 const int N=;

 int f[N];

 int n;

 char s[];

 int min(int a,int b)

 {

     if(a<b) return a;

     return b;

 }

 int can(int x)//x代表的是从原来串中取得的子串，比如abcdef，如果x=111000，那么就是取abc，1代表取，0代表不取

 {

     int i,j;

     int l=,r=n-;

     while (l<=r)

     {

         /*两个while是将开头和结尾的每一对1取出来比较*/

         while (l<n&&(x&(<<l))==) l++;//当遇到1或l>n时跳出

         while (r>=&&(x&(<<r))==) r--;

         if (s[l]!=s[r]) return ;//如果取出来的子串不满足回文就返回0

         else

         {

             l++;r--;//继续取对1

         }

     }

     return ;

 }

 int main()

 {

     int i,j;

     int ca;

     scanf("%d",&ca);

     while (ca--)

     {

         scanf("%s",s);

         n=strlen(s);

         f[]=;//一个都不取

         for (i=;i<(<<n);i++)//遍历所有状态，其实可以开个数组，记录一下满足的状态，那样可以省时间吗

         {

             if (can(i)) f[i]=;//满足回文就可以一步删除

             else f[i]=;//不满足就置为一个大于n的数

         }

         for (i=;i<(<<n);i++)//遍历所有状态

             for (j=(i-)&i;j;j=(j-)&i)//删除操作，j是i的下一个状态

                 f[i]=min(f[i],f[j]+f[i^j]);//i^j是在i中删除j剩下的状态，不如1001^1000=0001,0001就是删除1000剩下的

         printf("%d\n",f[(<<n)-]);//结果就是删除n个1需要的最小步数，n个1代表n个都要取到

     }

     return ;

 }