#include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int MAX =  + ;

 const int INF = 0x3f3f3f3f;

 char str1[MAX],str2[MAX];

 int dp[MAX][MAX],res[MAX][MAX];

 int start1[],End1[],start2[],End2[],vis[];

 int n,m;

 int main()

 {

     int tase;

     scanf("%d", &tase);

     while(tase--)

     {

         scanf("%s%s", str1 + ,str2 + );

         n = strlen(str1 + );

         m = strlen(str2 + );

         memset(vis, , sizeof(vis));

         memset(End1, -, sizeof(End1));

         memset(End2, -, sizeof(End2));

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

             start1[i] = start2[i] = INF;

         for(int i = ; i <= n; i++)

         {

             if(start1[str1[i] - 'A'] == INF)

                 start1[str1[i] - 'A'] = i;

             End1[str1[i] - 'A'] = i;

         }

         for(int i = ; i <= m; i++)

         {

             if(start2[str2[i] - 'A'] == INF)

                 start2[str2[i] - 'A'] = i ;

             End2[str2[i] - 'A'] = i;

         }

         memset(res, , sizeof(res));

         for(int i = ; i <= n; i++)

         {

             for(int j = ; j <= m; j++)

             {

                 int cnt = ;

                 for(int k = ; k < ; k++)

                 {

                     if(start1[k] == INF && start2[k] == INF)

                         continue;

                     if(start1[k] > i && start2[k] > j)

                         continue;

                     if(End1[k] <= i && End2[k] <= j)

                         continue;

                     cnt++;

                 }

                 res[i][j] = cnt;

             }

         }

         dp[][] = ;

         for(int i = ; i <= m ; i++)

             dp[][i] = dp[][i - ] + res[][i];

         for(int j = ; j <= n; j++)

             dp[j][] = dp[j - ][] + res[j][];

         for(int i = ; i <= n; i++)

         {

             for(int j = ; j <= m; j++)

             {

                 dp[i][j] = min(dp[i - ][j], dp[i][j - ]) + res[i][j];

             }

         }

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

     }

     return ;

 }