#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second

int dp[6200][6200]={};
int count(string s,int x,int y)
{
    if(x>=y)
    return 0;
    if(dp[x][y]!=-1)
    return dp[x][y];
    if(s[x]==s[y])
    return dp[x][y]=count(s,x+1,y-1);
    
    else
    return dp[x][y]=min(1+count(s,x,y-1),1+count(s,x+1,y));
    
}
int  main()
{
    IOS;
    int t;
    cin>>t;
     while(t--)
    {
       string s;
       cin>>s;
       memset(dp,-1,sizeof dp);
       int y=count(s,0,s.length()-1);
       cout<<y<<endl;
    }
}