#include<bits/stdc++.h>
using namespace std;
int dp[6101][6101];
int lcs(string &str,string &pat,int i,int j){
if(i==str.length()||j==pat.length()){
return 0;
}
if(dp[i][j]!=-1)
return dp[i][j];
if(str[i]==pat[j]){
return dp[i][j]=(1+lcs(str,pat,i+1,j+1));
}
return dp[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));
cout<<(str.length()-lcs(str,rev,0,0))<<endl;
}
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKaW50IGRwWzYxMDFdWzYxMDFdOwppbnQgbGNzKHN0cmluZyAmc3RyLHN0cmluZyAmcGF0LGludCBpLGludCBqKXsKICAgIGlmKGk9PXN0ci5sZW5ndGgoKXx8aj09cGF0Lmxlbmd0aCgpKXsKICAgICAgICByZXR1cm4gMDsKCiAgICB9CiAgICBpZihkcFtpXVtqXSE9LTEpCiAgICAgICAgcmV0dXJuIGRwW2ldW2pdOwogICAgaWYoc3RyW2ldPT1wYXRbal0pewogICAgICAgIHJldHVybiBkcFtpXVtqXT0oMStsY3Moc3RyLHBhdCxpKzEsaisxKSk7CiAgICB9CiAgICByZXR1cm4gZHBbaV1bal09bWF4KGxjcyhzdHIscGF0LGkrMSxqKSxsY3Moc3RyLHBhdCxpLGorMSkpOwp9CmludCBtYWluKCl7CiAgICBpbnQgdDsKICAgIGNpbj4+dDsKICAgIHdoaWxlKHQtLSl7CiAgICAgICAgc3RyaW5nIHN0cjsKICAgICAgICBjaW4+PnN0cjsKICAgICAgICBzdHJpbmcgcmV2PXN0cjsKICAgICAgICByZXZlcnNlKHJldi5iZWdpbigpLHJldi5lbmQoKSk7CiAgICAgICAgLy9jb3V0PDxyZXY7CiAgICAgICAgbWVtc2V0KGRwLC0xLHNpemVvZihkcCkpOwogICAgICAgIGNvdXQ8PChzdHIubGVuZ3RoKCktbGNzKHN0cixyZXYsMCwwKSk8PGVuZGw7CgogICAgfQoKfQo=