#include<bits/stdc++.h>
using namespace std;
char s1[110],s2[110];
string a,b;
int n,m,s;
int main(){
    freopen("painter.in","r",stdin);
    freopen("painter.out","w",stdout);
    while(cin>>a>>b){
        int l=a.size();
        int dp[110][110];
        for(int i=0;i<=l-1;i++){
            s1[i+1]=a[i];
            s2[i+1]=b[i];
        }
        for(int i=1;i<=l;i++){
            dp[i][i]=1;
        }
        for(int len=2;len<=l;len++){
            for(int i=1;i<=l-len+1;i++){
                int j=i+len-1;
                dp[i][j]=0x3f3f3f3f;
                if(s2[i]==s2[j]){
                    dp[i][j]=min(dp[i+1][j],dp[i][j-1]);
                }else{
                    for(int k=i;k<j;k++){
                        dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
                    }
                }                
            }
        }
        for(int i=1;i<=l;i++){
            if(s1[i]==s2[i]){
                dp[1][i]=dp[1][i-1];
            }else{
            for(int j=1;j<i;j++){
                dp[1][i]=min(dp[1][i],dp[1][j]+dp[j+1][i]);
            }}
        }        
        cout<<dp[1][l]<<endl;

    }
    
    return 0;
}