minimum number of deletions to make a string palindrome
//Code by @soumyadeepp : Soumyadeep Ghosh
//A very Simple DP problem. Just find the length of the Longest common subsequence
//of the string and its reverse. Now subtract this length from the actual length
//of the substring. That's it.
#include <bits/stdc++.h>
using namespace std;
int lps(string s)
{
string r = s;
reverse(r.begin(),r.end());
int sz1 = s.size();
int dp[sz1+1][sz1+1];
for(int i = 0 ; i <= sz1 ; i++)
{
dp[0][i] = 0;
dp[i][0] = 0;
}
for(int i = 1; i <= sz1; i++)
{
for(int j = 1; j <= sz1 ; j++)
{
if(s[i-1] == r[j-1])
{
dp[i][j] = dp[i-1][j-1] + 1;
}
else
dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
}
}
return dp[sz1][sz1];
}
int main()
{
int t;
cin>>t;
while(t--)
{
string s;
cin>>s;
int ans = s.size() - lps(s);
cout<<ans<<endl;
}
}