#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
int f[2002][2002];
char a[2002], b[2002];
int main(){
	int t;
	scanf("%d", &t);
	while (t--){
		memset(f, 127 / 3, sizeof(f));
		scanf("%s%s", a, b);
		int n = strlen(a), m = strlen(b);
		for (int i = 0; i < n; i++) f[i][0] = i;/////
		for (int i = 0; i < m; i++) f[0][i] = i;/////
		for (int i = 1; i <= n; i++)
		    for (int j = 1; j <= m; j++){
    			if (a[i-1] == b[j-1]) f[i][j] = f[i-1][j-1];
		        else f[i][j] = min(min(f[i-1][j], f[i][j-1]), f[i-1][j-1]) + 1;
    		}		        
        printf("%d\n", f[n][m]);
	}
	return 0;
}