C++ :

#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#include<stack>
#include<iostream>
#include<queue>
#include<cmath>
#include<string>
#include<set>
#include<map>
using namespace std;
const int maxn = 100 + 5;
const int mod = 1000000000 + 7;
const double eps = 1e-7;
const int INF = 1000000000;
typedef long long LL;
typedef pair<int, int> P;

char s[maxn];
int dp[maxn][maxn];

int solve(int s1, int e1, int s2, int e2){
            memset(dp, 0, sizeof dp);
            int tag = 0;
            for(int i = s2;i <= e2;i++){
                if(s[0]==s[i])
                    tag = 1;
                if(tag)
                    dp[0][i] = i-s2;
                else
                    dp[0][i] = i-s2+1;
            }
            tag = 0;
            for(int i = s1;i <= e1;i++){
                if(s[s2]==s[i])
                    tag = 1;
                if(tag == 1)
                    dp[i][s2] = i-s1;
                else
                    dp[i][s2] = i-s1+1;
            }

            for(int i = s1+1;i <= e1;i++){
                for(int j = s2+1;j <= e2;j++){
                    if(s[i]==s[j])
                        dp[i][j] = dp[i-1][j-1];
                    else{
                        dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1]))+1;
                    }
                }
            }
            return dp[e1][e2];
}

int main(){
    int t;
    scanf("%d", &t);
    while(t--){
        scanf("%s", s);
        int n = strlen(s);
        if(n == 1){
            printf("1\n");
            continue;
        }
        int ans = n;
        int s1 = 0, e1;
        int s2, e2 = n-1;
        for(int i = 0;i < n-1;i++){
            e1 = i;
            s2 = i+1;
            //cout << solve(s1, e1, s2, e2) << endl;
            ans = min(ans, solve(s1, e1, s2, e2));
        }
        printf("%d\n", ans);


    }
    return 0;
}