#include<bits/stdc++.h>
using namespace std;

int d[25][25];
int path[25][25];


int main(){
	string a,b;
	while(cin>>a){
		int m,n;
		if(a.compare("#")==0){
			break;
		}
		cin>>b;
		m=a.length();
		n=b.length();

		d[0][0]=0;
		for(int i=1;i<m;i++) d[i][0]=i;
		for(int i=1;i<n;i++) d[0][i]=i;

		for(int i=0;i<m;i++){
			for(int j=0;j<n;j++){
				int val;
				if(a[i]==b[i]) val=0;
				else val=1;



				d[i][j]=min(d[i-1][j-1]+val,min(d[i-1][j]+1,d[i][j-1]+1));
			}
		}
		cout<<d[m-1][n-1]<<endl;
	}
	return 0;
}