#include<cstdio>

 #include<cmath>

 #include<cctype>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<vector>

 #include<queue>

 #include<set>

 #include<map>

 #include<stack>

 #include<string>

 #define lc(a) (a<<1)

 #define rc(a) (a<<1|1)

 #define MID(a,b) ((a+b)>>1)

 #define fin(name)  freopen(name,"r",stdin)

 #define fout(name) freopen(name,"w",stdout)

 #define clr(arr,val) memset(arr,val,sizeof(arr))

 #define _for(i,start,end) for(int i=start;i<=end;i++)

 #define FAST_IO ios::sync_with_stdio(false);cin.tie(0);

 using namespace std;

 typedef long long LL;

 const int N=5e2+;

 const int INF=0x3f3f3f3f;

 const double eps=1e-;

 int ans[N],dp[N][N];

 char str[N],_str[N];

 int main(){

     while(~scanf("%s",str)){

         scanf("%s",_str);

         int n=strlen(str);

         for(int i=;i<n;i++){

             dp[i][i]=;

         }

         //写法跟lightoj 1422 那个换装类似

         for(int len=;len<n;len++){

             for(int i=;i+len<n;i++){

                 int j=i+len;

                 dp[i][j]=dp[i][j-]+;

                 for(int k=i;k<=j;k++){

                     dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+][j]);

                 }

                 if(_str[i]==_str[j])

                     dp[i][j]--;

             }

         }

         for(int i=;i<n;i++){

            ans[i]=dp[][i];

            if(str[i]==_str[i]){

                 if(i==) ans[]=;

                 else ans[i]=ans[i-];

            }

            for(int j=;j<i;j++)

             ans[i]=min(ans[i],ans[j]+dp[j+][i]);

         }

         printf("%d\n",ans[n-]);

     }

     return ;

 }