#include<cstdio>

 #include<iostream>

 #include<algorithm>

 #include<math.h>

 #include<string.h>

 #include<vector>

 #include<queue>

 #include<map>

 #include<iterator>

 #include<vector>

 #include<set>

 #define INF 9999999

 typedef long long ll;

 const int Max=(<<)+;

 using namespace std;

 int dp[][];//dp[i][j]表示从i~j的刷法

 int ans[]; 

 int main()

 {

     string str1,str2;

     int len;

     while(cin>>str1>>str2)

     {

         len=str1.length();

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

         {

             for(int i=j;i>=;i--)

             {

                 dp[i][j]=dp[i+][j]+;//逐个更新区间i~j内的值

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

                 {

                     if(str2[i]==str2[k])//若遇到相同的则需寻找区间的最小值

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

                 }

             }

         }

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

             ans[i]=dp[][i];//ans[i]表示区间[0,i]需要刷的值

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

         {

             if(str1[i]==str2[i])//碰到相同的值选择不刷

                 ans[i]=ans[i-];

             else

             {

                 for(int j=;j<i;j++)//寻找最优解

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

             }

         }

         cout<<ans[len-]<<endl;

     }

     return ;

 }