#include <iostream>#include <algorithm>#include <stdio.h>#include <string.h>using namespace std;char x[5050], y[55];int len, n;int f[110][55];int g[5050][110];int opt[5050];void init(){scanf("%s%s", y, x);len = strlen(y); n = strlen(x);}int abs(int x){if (x<0) return -x;return x;}void solve(){memset(g, 0x3f, sizeof g);for (int st=1; st<=n; st++){memset(f, 0x3f, sizeof f);f[0][0] = 0;for(int i=1;i<=2*len;i++) f[i][0]=i;for(int j=1;j<=len;j++) f[0][j]=j;for (int i=st; i<st+2*len && i<=n; i++){for (int j=1; j<=len; j++){if (x[i-1] == y[j-1]) { f[i-st+1][j] = min(f[i-st+1][j], f[i-st][j-1]);}else { f[i-st+1][j] = min(f[i-st+1][j], f[i-st][j-1]+1);}f[i-st+1][j] = min(f[i-st+1][j], min(f[i-st][j]+1, f[i-st+1][j-1]+1));}}for (int i=1; i<=2*len; i++) { g[st][i] = f[i][len];}}memset(opt, 0x3f, sizeof opt);opt[0] = 0;for (int i=1; i<=n; i++){for (int j=max(0, i-2*len-1); j<i; j++){int sublen = i-j;int er = g[j+1][sublen];opt[i] = min(opt[i], max(opt[j], er));}}if(opt[n]>100000) while(1)printf("11111111n");printf("%dn", opt[n]);}int main(){int test; scanf("%d", &test);while (test--){init();solve();}}
