#include<bits/stdc++.h>
using namespace std;
map<string,int> mp;
map<string,int> present;
int minChars(string& s,int i,int j)
{
if(i>=j)
return 0;
if(s[i]==s[j])
return minChars(s,i+1,j-1);
else
{
if(present[s])
return mp[s];
else
{
string a=s[j]+s.substr(i,j-i+1);
string b=s.substr(i,j-i+1)+s[i];
int p,q,r,s;
p=r=0;
q=a.length()-1;
s=b.length()-1;
mp[s]=min(1+minChars(a,p,q),1+minChars(b,r,s));
present[s]=1;
return mp[s];
}
}
}
int main()
{
int t;
cin>>t;
string s;
while(t--)
{
cin>>s;
int k=minChars(s,0,s.length()-1);
cout<<k;
cout<<endl;
}
return 0;
}