#include<bits/stdc++.h>
using namespace std;
map <pair<int,int>,int> dp;
int lcs(string &str,string &pat,int i,int j){
if(i==str.length()||j==pat.length()){
return 0;
}
if(dp.count(make_pair(i,j)))
return dp[make_pair(i,j)];
if(str[i]==pat[j]){
return dp[make_pair(i,j)]=(1+lcs(str,pat,i+1,j+1));
}
return dp[make_pair(i,j)]=max(lcs(str,pat,i+1,j),lcs(str,pat,i,j+1));
}
int main(){
int t;
cin>>t;
while(t--){
string str;
cin>>str;
string rev=str;
reverse(rev.begin(),rev.end());
//cout<<rev;
//memset(dp,-1,sizeof(dp));
dp.clear();
cout<<(str.length()-lcs(str,rev,0,0))<<endl;
}
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKbWFwIDxwYWlyPGludCxpbnQ+LGludD4gZHA7CmludCBsY3Moc3RyaW5nICZzdHIsc3RyaW5nICZwYXQsaW50IGksaW50IGopewogICAgaWYoaT09c3RyLmxlbmd0aCgpfHxqPT1wYXQubGVuZ3RoKCkpewogICAgICAgIHJldHVybiAwOwoKICAgIH0KICAgIGlmKGRwLmNvdW50KG1ha2VfcGFpcihpLGopKSkKICAgICAgICByZXR1cm4gZHBbbWFrZV9wYWlyKGksaildOwogICAgaWYoc3RyW2ldPT1wYXRbal0pewogICAgICAgIHJldHVybiBkcFttYWtlX3BhaXIoaSxqKV09KDErbGNzKHN0cixwYXQsaSsxLGorMSkpOwogICAgfQogICAgcmV0dXJuIGRwW21ha2VfcGFpcihpLGopXT1tYXgobGNzKHN0cixwYXQsaSsxLGopLGxjcyhzdHIscGF0LGksaisxKSk7Cn0KaW50IG1haW4oKXsKICAgIGludCB0OwogICAgY2luPj50OwogICAgd2hpbGUodC0tKXsKICAgICAgICBzdHJpbmcgc3RyOwogICAgICAgIGNpbj4+c3RyOwogICAgICAgIHN0cmluZyByZXY9c3RyOwogICAgICAgIHJldmVyc2UocmV2LmJlZ2luKCkscmV2LmVuZCgpKTsKICAgICAgICAvL2NvdXQ8PHJldjsKICAgICAgICAvL21lbXNldChkcCwtMSxzaXplb2YoZHApKTsKICAgICAgICBkcC5jbGVhcigpOwogICAgICAgIGNvdXQ8PChzdHIubGVuZ3RoKCktbGNzKHN0cixyZXYsMCwwKSk8PGVuZGw7CgogICAgfQoKfQo=