#include <iostream>
using namespace std;
 
long long int s[2001][2001];
 
int main() {
	int t;
	string a,b;
	long long int i,j;
	for(i=0;i<2001;i++)
	{
		s[i][0]=i;
		s[0][i]=i;
	}
	cin>>t;
	while(t>0)
	{
		cin>>a>>b;
		t--;
		for(i=1;i<=a.length();i++)
		{
			for(j=1;j<=b.length();j++)
			{
				if(a[i-1] == b[j-1])
					s[i][j]=s[i-1][j-1];
				else
					s[i][j] = min(min(s[i-1][j],s[i-1][j-1]),s[i][j-1]) + 1;
			}
		}
		cout<<s[i-1][j-1]<<"\n";
	}
	return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKbG9uZyBsb25nIGludCBzWzIwMDFdWzIwMDFdOwoKaW50IG1haW4oKSB7CglpbnQgdDsKCXN0cmluZyBhLGI7Cglsb25nIGxvbmcgaW50IGksajsKCWZvcihpPTA7aTwyMDAxO2krKykKCXsKCQlzW2ldWzBdPWk7CgkJc1swXVtpXT1pOwoJfQoJY2luPj50OwoJd2hpbGUodD4wKQoJewoJCWNpbj4+YT4+YjsKCQl0LS07CgkJZm9yKGk9MTtpPD1hLmxlbmd0aCgpO2krKykKCQl7CgkJCWZvcihqPTE7ajw9Yi5sZW5ndGgoKTtqKyspCgkJCXsKCQkJCWlmKGFbaS0xXSA9PSBiW2otMV0pCgkJCQkJc1tpXVtqXT1zW2ktMV1bai0xXTsKCQkJCWVsc2UKCQkJCQlzW2ldW2pdID0gbWluKG1pbihzW2ktMV1bal0sc1tpLTFdW2otMV0pLHNbaV1bai0xXSkgKyAxOwoJCQl9CgkJfQoJCWNvdXQ8PHNbaS0xXVtqLTFdPDwiXG4iOwoJfQoJcmV0dXJuIDA7Cn0=

MQpGT09ECk1PTkVZ

1
FOOD
MONEY