void solve(){
    string a,b;
    cin >> a >> b;
    vector<vector<int>>dp(N,vector<int>(N,-1));
    int n = sz(a), m = sz(b);
    function<int(int,int)>calc=[&](int i,int j)->int{
        if(i==n&&j==m)
            return 0;
        if(i>n||j>m)
            return INT_MAX;
        if(~dp[i][j])
            return dp[i][j];
        int op1 = calc(i,j+1)+1;
        int op2 = calc(i+1,j)+1;
        int op3 = calc(i+1,j+1)+(a[i]!=b[j]);
        return dp[i][j] = min({op1,op2,op3});
    };
    cout << calc(0,0);
}

vector<vector<int>>dp(N,vector<int>(N,-1));
int n,m;
string a,b;
int calc(int i,int j){
    if(i==n&&j==m)
        return 0;
    if(i>n||j>m)
        return INT_MAX;
    if(~dp[i][j])
        return dp[i][j];
    int op1 = calc(i,j+1)+1;
    int op2 = calc(i+1,j)+1;
    int op3 = calc(i+1,j+1)+(a[i]!=b[j]);
    return dp[i][j] = min({op1,op2,op3});
}
void solve() {
    cin >> a >> b;
    n = sz(a), m = sz(b);
    cout << calc(0,0);
}