#include<bits/stdc++.h>
#define ll long long 
#define N 105
using namespace std;

ll Min(ll a,ll b){return a<b?a:b;}
ll Max(ll a,ll b){return a>b?a:b;}

ll f[N][N],ans[N];
char st[N],s[N];

int main(){
	while(scanf("%s%s",st+1,s+1)==2){
		memset(f,127,sizeof(f));
		memset(ans,127,sizeof(ans));
		ll len=strlen(st+1);
		for(int i=1;i<=len;++i)f[i][i]=1;
		for(int k=1;k<=len-1;++k){
			for(int i=1;i<=len-k;++i){
				int l=i,r=k+i;
				if(s[l]==s[r])f[l][r]=Max(f[l+1][r],f[l][r-1]);
				else {
					for(int j=l;j<=r;++j){
						f[l][r]=Min(f[l][r],f[l][j]+f[j+1][r]);
					}
				}
			}
		}
		if(st[1]==s[1])ans[1]=0;
		else ans[1]=1;
		for(int i=2;i<=len;++i){
			if(s[i]==st[i])ans[i]=ans[i-1];
			else {
				for(int k=1;k<=i-1;++k){
					ans[i]=Min(ans[i],ans[k]+f[k+1][i]);
				}
			}
			ans[i]=Min(ans[i],f[1][i]);
		}
		cout<<ans[len]<<endl;
	}
	return 0;
}