#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;
}
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiAKI2RlZmluZSBJT1MgaW9zOjpzeW5jX3dpdGhfc3RkaW8oMCk7IGNpbi50aWUoMCk7IGNvdXQudGllKDApOwojZGVmaW5lIGVuZGwgIlxuIgojZGVmaW5lIGxsIGxvbmcgbG9uZwojZGVmaW5lIHBiIHB1c2hfYmFjawojZGVmaW5lIG1wIG1ha2VfcGFpcgojZGVmaW5lIGZpIGZpcnN0CiNkZWZpbmUgc2Ugc2Vjb25kCiAKaW50IGRwWzYyMDBdWzYyMDBdPXt9OwppbnQgY291bnQoc3RyaW5nICZzLGludCB4LGludCB5KQp7CiAgICBpZih4Pj15KQogICAgcmV0dXJuIDA7CiAgICBpZihkcFt4XVt5XSE9LTEpCiAgICByZXR1cm4gZHBbeF1beV07CiAgICBpZihzW3hdPT1zW3ldKQogICAgcmV0dXJuIGRwW3hdW3ldPWNvdW50KHMseCsxLHktMSk7CiAKICAgIGVsc2UKICAgIHJldHVybiBkcFt4XVt5XT1taW4oMStjb3VudChzLHgseS0xKSwxK2NvdW50KHMseCsxLHkpKTsKIAp9CmludCAgbWFpbigpCnsKICAgIElPUzsKICAgIGludCB0OwogICAgY2luPj50OwogICAgIHdoaWxlKHQtLSkKICAgIHsKICAgICAgIHN0cmluZyBzOwogICAgICAgY2luPj5zOwogICAgICAgbWVtc2V0KGRwLC0xLHNpemVvZiBkcCk7CiAgICAgICBpbnQgeT1jb3VudChzLDAscy5sZW5ndGgoKS0xKTsKICAgICAgIGNvdXQ8PHk8PGVuZGw7CiAgICB9Cn0g