#include <iostream>
using namespace std;
 
 
int main() {
	int t;
	string a,b;
	long long int i,j;
 
	long long int s[2001][2001]; //declared locally
 
	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;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwogCiAKaW50IG1haW4oKSB7CglpbnQgdDsKCXN0cmluZyBhLGI7Cglsb25nIGxvbmcgaW50IGksajsKCQoJbG9uZyBsb25nIGludCBzWzIwMDFdWzIwMDFdOyAvL2RlY2xhcmVkIGxvY2FsbHkKCQoJZm9yKGk9MDtpPDIwMDE7aSsrKQoJewoJCXNbaV1bMF09aTsKCQlzWzBdW2ldPWk7Cgl9CgljaW4+PnQ7Cgl3aGlsZSh0PjApCgl7CgkJY2luPj5hPj5iOwoJCXQtLTsKCQlmb3IoaT0xO2k8PWEubGVuZ3RoKCk7aSsrKQoJCXsKCQkJZm9yKGo9MTtqPD1iLmxlbmd0aCgpO2orKykKCQkJewoJCQkJaWYoYVtpLTFdID09IGJbai0xXSkKCQkJCQlzW2ldW2pdPXNbaS0xXVtqLTFdOwoJCQkJZWxzZQoJCQkJCXNbaV1bal0gPSBtaW4obWluKHNbaS0xXVtqXSxzW2ktMV1bai0xXSksc1tpXVtqLTFdKSArIDE7CgkJCX0KCQl9CgkJY291dDw8c1tpLTFdW2otMV08PCJcbiI7Cgl9CglyZXR1cm4gMDsKfQ==

MQpGT09ECk1PTkVZ

1
FOOD
MONEY