#include <bits/stdc++.h>
using namespace std;
const int N=100+5;
const int inf=0x3f3f3f3f;
int n,q;
char c[N],s[N];
int f[N][N];
int dp(int l,int r,int se){
    if(l==r&&c[l]==se)
    return 0;
	if (l==r)
    return f[l][r]=1;
	if (f[l][r]!=inf)
    return f[l][r];
	if (s[l]==s[r])
    f[l][r]=min(f[l][r],min(dp(l+1,r,s[l]),dp(l,r-1,s[l])));
	else{
		for (int k=l;k<=r-1;k++)f[l][r]=min(f[l][r],dp(l,k,se)+dp(k+1,r,se));
	}
	return f[l][r];
}
int main(){
	freopen ("painter.in","r",stdin);
	freopen ("painter.out","w",stdout);
    while(scanf("%s%s",c+1,s+1)){
	    n=strlen(s+1);
	    memset(f,0x3f,sizeof(f));
	    cout<<dp(1,n,-1)<<endl;
    }
	return 0;
}