#include <bits/stdc++.h>
using namespace std;
#define sz(v)    ((int)((v).size()))
#define Rep(i, n) for(int i = 0; i < sz(n); ++i)
#define lp(i, n)  for(int i=0;i<=(int)(n);++i)
#define All(X)  (X).begin(),(X).end()
#define All2(X)  (X).rebegin(),(X).rend()
#define MOD 1000000000 + 7
#define MAX (int)1e5+4
#define PI 2 * acos(0.0)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;

int mem[2001][2001], t, i, j, sz1, sz2;
char str1[2001], str2[2001];

int dp(int i, int j) {
	if (i == sz1)
		return sz2 - j;
	if (j == sz2)
		return sz1 - i;
	int &ret = mem[i][j];
	if (ret != -1)
		return ret;
	if (str1[i] == str2[j])
		return ret = dp(i + 1, j + 1);

	int cho1 = dp(i + 1, j) + 1;
	int cho2 = dp(i, j + 1) + 1;
	int cho3 = dp(i + 1, j + 1) + 1;
	return ret = min(cho1, min(cho2, cho3));
}
int main() {
#ifndef ONLINE_JUDGE
	freopen("myfile.in", "r", stdin);
#endif
	scanf("%d", &t);
	while (t--) {
		memset(mem, -1, sizeof mem);
		scanf("%s%s", str1, str2);
		sz1 = strlen(str1), sz2 = strlen(str2);
		printf("%d\n", dp(0, 0));
	}
	return 0;
}