//UVA1625ColorLength
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 5000 + 10;
const int INF = 1e6;
int d[2][MAXN * 2], c[2][MAXN * 2], cost[2][MAXN * 2], sp[MAXN], sq[MAXN], ep[MAXN], eq[MAXN];
char p[MAXN], q[MAXN];
int main() {
int T;
scanf("%d", &T);
while(T--) {
scanf("%s%s", p + 1, q + 1);
int n = strlen(p + 1), m = strlen(q + 1);
memset(d, 0, sizeof(d));
memset(cost, 0, sizeof(cost));
for(int i = 1; i <= n; i++) p[i] -= 'A';
for(int i = 1; i <= m; i++) q[i] -= 'A';
for(int i = 0; i < 26; i++) {
sp[i] = sq[i] = INF; ep[i] = eq[i] = 0;
}
for(int i = 1; i <= n; i++) {
sp[p[i]] = min(sp[p[i]], i);
ep[p[i]] = i;
}
for(int i = 1; i <= m; i++) {
sq[q[i]] = min(sq[q[i]], i);
eq[q[i]] = i;
}
int t = 0;//辅助，用来存储上一次移动i时的一切关于d的记录
for(int i = 0; i <= n; i++) {
for(int j = 0; j <= m; j++) {
if(!i && !j) continue;
int v1 = INF, v2 = INF;
if(i) v1 = d[t^1][j] + cost[t^1][j];//调用上一次的最小值
if(j) v2 = d[t][j - 1] + cost[t][j - 1];//计算本轮上一次移动j后的最小值
d[t][j] = min(v1, v2);//得出当前的最优值
if(i) {
cost[t][j] = cost[t^1][j];
if(sp[p[i]] == i && sq[p[i]] > j) cost[t][j]++;
//p[i]是p的开头，且是整个链的此字母的开头
if(ep[p[i]] == i && eq[p[i]] <= j) cost[t][j]--;
//
}
else if(j) {
cost[t][j] = cost[t][j - 1];
if(sq[q[j]] == j && sp[q[j]] > i) cost[t][j]++;
if(eq[q[j]] == j && ep[q[j]] <= i) cost[t][j]--;
}
}
t ^= 1;
}
printf("%d\n", d[t^1][m]);
}
return 0;
}
/*
2
AAABBCY
ABBBCDEEY
GBBY
YRRGB
*/
