#include<iostream>
#include<string>
#include<stdio.h>
#include<algorithm>
using namespace std;
int main()
{
    int t;unsigned int m,n;
    int **edit=new int*[2001]; bool flag;
    for(unsigned int k=0;k<2001;k++){edit[k]=new int[2001];}

    string::iterator i,j;
    scanf("%d",&t);getchar();
    while(t--)//test cases
    {
        string *a=new string;
        string *b=new string;
        getline(cin,*a);m=(*a).length()+1;//cout<<m;
        getline(cin,*b);n=(*b).length()+1;//cout<<n;

        for(unsigned int x=0;x<m;x++)
        {
            for(unsigned int y=0;y<n;y++)
            {
                if(x==0&&y==0){edit[x][y]=0;}
                else if(x==0){edit[x][y]=edit[x][y-1]+1;}//insert operation
                else if(y==0){edit[x][y]=edit[x-1][y]+1;}//delete operation
                else
                {   i=(*a).begin()+x-1;j=(*b).begin()+y-1;
                    if(*i==*j){ flag=0;}
                    else {flag=1;}
                        edit[x][y]=min(min(edit[x-1][y-1]+flag,edit[x-1][y]+1),edit[x][y-1]+1);
                    
                }
            }
        }

printf("%d\n",edit[m-1][n-1]);
delete a;
delete b;
}
    return 0;
}