/*By DennyQi 2019*/

#include <cstdio>

#include <queue>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

const int MAXN = ;

const int MAXM = ;

const int INF = 0x3f3f3f3f;

inline int Max(const int a, const int b){ return (a > b) ? a : b; }

inline int Min(const int a, const int b){ return (a < b) ? a : b; }

inline int read(){

    int x = ; int w = ; register char c = getchar();

    for(; c ^ '-' && (c < '' || c > ''); c = getchar());

    if(c == '-') w = -, c = getchar();

    for(; c >= '' && c <= ''; c = getchar()) x = (x<<) + (x<<) + c - ''; return x * w;

}

int T,dp[],cnt[],lsta[],lstb[],fsta[],fstb[],la,lb;

char a[],b[];

inline void Init_cnt(){

    memset(lsta,,sizeof(lsta));

    memset(lstb,,sizeof(lstb));

    memset(fsta,0x3f,sizeof(fsta));

    memset(fstb,0x3f,sizeof(fstb));

    for(int i = ; i <= la; ++i){

        lsta[a[i]-'A'] = max(lsta[a[i]-'A'],i);

        fsta[a[i]-'A'] = min(fsta[a[i]-'A'],i);

    }

    for(int i = ; i <= lb; ++i){

        lstb[b[i]-'A'] = max(lstb[b[i]-'A'],i);

        fstb[b[i]-'A'] = min(fstb[b[i]-'A'],i);

    }

}

inline void DP(){

    memset(dp,INF,sizeof(dp));

    memset(cnt,,sizeof(cnt));

    char cur;

    dp[] = ;

    for(int i = ; i <= la; ++i){

        for(int j = ; j <= lb; ++j){

            if(i== && j==) continue;

            if(i == ){

                cnt[j] = cnt[j-];

                cur = b[j]-'A';

                if(j == fstb[cur]) ++cnt[j];

                if(j == lstb[cur] && lsta[cur] == ) --cnt[j];

            }

            else{

                cur = a[i]-'A';

                if(j >= lstb[cur] && i >= lsta[cur]) --cnt[j];

                if(j < fstb[cur] && i == fsta[cur]) ++cnt[j];

            }

            dp[j] = min((j==)?INF:dp[j-], (i==)?INF:dp[j])+cnt[j];

        }

    }

}

int main(){

    scanf("%d",&T);

    while(T--){

        scanf("%s%s",a+,b+);

        la = strlen(a+), lb = strlen(b+);

        Init_cnt();

        DP();

        printf("%d\n",dp[lb]);

    }

    return ;

}