#define filer() freopen("D.txt","r",stdin)
#define filew() freopen("out.txt","w",stdout)
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<stack>
#include<string>
#include<vector>
#include <map>
#define INF 1<<29
#define PI pair<int,int>

#define SET(a, x) memset((a), (x), sizeof(a))
#define pb push_back
#define i64 long long
#define EPS (1e-9)
using namespace std;
typedef vector<int> VI;
typedef vector<PI> vii;
//i64 INF=(i64)((i64)1<<(i64)59);

int N;

char s1[210];
char s2[210];

int DP[210][210][4];

int func(int i,int j,int state)
{
    if(DP[i][j][state]!=-1)return DP[i][j][state];

    if(i==j)
    {
        if(state==0)
        {
            if(s1[i]==s2[i])return DP[i][j][state]=0;
            return DP[i][j][state]=1;
        }
        else if(state==1)
        {
            if(s2[i]=='A')return DP[i][j][state]=0;
            return DP[i][j][state]=1;
        }
        else
        {
            if(s2[i]=='B')return DP[i][j][state]=0;
            return DP[i][j][state]=1;
        }
    }



    int ans=INF,a,b,c,x,y,k;

    for(k=i;k<j;k++)
    {
        a=func(i,k,state);
        b=func(k+1,j,state);
        ans=min(ans,a+b);
    }
    if(state!=1){
        for(k=i;k<j;k++)
        {
            a=func(i,k,1);
            b=func(k+1,j,1);
            ans=min(ans,1+a+b);
        }
    }

    if(state!=2){
        for(k=i;k<j;k++)
        {
            a=func(i,k,2);
            b=func(k+1,j,2);
            ans=min(ans,1+a+b);
        }
    }
    /*for(int k=i;k<j;k++)
    {
        a=func(i,k,state);
        b=1+func(i,k,1);
        c=1+func(i,k,2);
        x=min(a,b);
        x=min(x,c);
        a=func(k+1,j,state);
        b=1+func(k+1,j,1);
        c=1+func(k+1,j,2);
        y=min(a,b);
        y=min(y,c);

        ans=min(ans,x+y);
    }*/
    return DP[i][j][state]=ans;
}

int main()
{
    filer();
    int T,cas=0;
    int i,j,k;
    scanf("%d",&T);
    SET(DP,-1);
    while(T--)
    {

        scanf("%s",s1);
        scanf("%s",s2);
        int l=strlen(s1);
        int ans=func(0,l-1,0);
        //cout<<ans<<endl;
        printf("%d\n",ans);
        if(T)
        {
            for(i=0;i<l;i++)
            {
                for(j=0;j<l;j++)
                {
                    for(k=0;k<3;k++)DP[i][j][k]=-1;
                }
            }
        }
    }

    return 0;
}
/*
Test Case:

*/