#include <bits/stdc++.h>
using namespace std;
char a[1100],b[1100];
int dp[110][110];
int main(){
    freopen("painter.in","r",stdin);
    freopen("painter.out","w",stdout);
    while(cin>>a+1>>b+1){
        memset(dp,0x3f,sizeof(dp));
        int lb = strlen(b+1);
        for(int i = 1;i <= lb;i++)dp[i][i] = 1;
        for(int len = 2;len <= lb;len++){
            for(int l = 1;l+len-1 <= lb;l++){
                int r = l+len-1;
                dp[l][r] = 0x3f3f3f3f;
                if(b[l] == b[r])dp[l][r] = min(dp[l+1][r],dp[l][r-1]);
                else{
                    for(int k = l;k < r;k++){
                    dp[l][r] = min(dp[l][r],dp[l][k]+dp[k+1][r]);
                }
                }
            }
        }
        for(int i = 1;i <= lb;i++){
            if(a[i] == b[i])dp[1][i] = dp[1][i-1];
            for(int j = 1;j < i;j++){
                dp[1][i] = min(dp[1][i],dp[1][j]+dp[j+1][i]); 
            }
        }
        printf("%d\n",dp[1][lb]);
    }
    
    return 0; 

}