#include <cstdio>
 
#define I_F "dna.in"
#define O_F "dna.out"
 
//A 0
//C 1
//G 2
//T 3
 
const int MAXl=3000+1;
 
short a[MAXl], b[MAXl];
int al, bl;
int ans;
bool f[MAXl][MAXl];
int g[MAXl][MAXl];
 
void Input();
inline int Min(const int&, const int&);
void Dynap();
void Output();
 
int main()
{
    int m;
    freopen(I_F,"r",stdin);
    freopen(O_F,"w",stdout);
    for (scanf("%d",&m); m>0; --m)
    {
        Input();
        Dynap();
        Output();
    }
    return 0;
}
 
void Input()
{
    al=bl=1;
    char t;
    do
    {
        scanf("%c",&t);
    } while (t!='A' && t!='C' && t!='G' && t!='T');
    do
    {
        if (t=='A')
            a[al]=0;
        else if (t=='C')
            a[al]=1;
        else if (t=='G')
            a[al]=2;
        else if (t=='T')
            a[al]=3;
        else
            break;
        scanf("%c",&t);
        al++;
    }while (true);
    do
    {
        scanf("%c",&t);
    } while (t!='A' && t!='C' && t!='G' && t!='T');
    do
    {
        if (t=='A')
            b[bl]=0;
        else if (t=='C')
            b[bl]=1;
        else if (t=='G')
            b[bl]=2;
        else if (t=='T')
            b[bl]=3;
        else
            break;
        scanf("%c",&t);
        bl++;
    }while (true);
    a[0]=-1;
    b[0]=-2;
    al--;
    bl--;
}
 
inline int Min(const int &a, const int &b)
{
    return (a<b)?a:b;
}
 
void Dynap()
{
    int i,j,k;
    for (i=0; i<MAXl; ++i)
        f[i][0]=true,
        g[i][0]=-1;
    for (i=1; i<MAXl; ++i)
        f[0][i]=false,
        g[0][i]=-1;
    g[0][0]=-2;
     
    for (j=1; j<=bl; ++j)
        for (i=1; i<=al; ++i)
            f[i][j]=(a[i]==b[j])?f[i-1][j-1]:f[i-1][j];
         
    for (j=1; j<=bl; ++j)
        for (i=1; i<=al; ++i)
            if (f[i][j]==false)
                g[i][j]=-1;
            else
                if (a[i]==b[j])
                {
                    for (k=1; k<=Min(i,j); )
                    	if (a[i-k]==b[j-k])
                    		++k;
                    	else
                    		break;
                    g[i][j]=g[i-k][j-k]+2;
                }
                else
                    g[i][j]=(a[i-1]!=b[j])?g[i-1][j]:(g[i-1][j]+1);
    ans=g[al][bl];
}
 
void Output()
{
    printf("%d\n",ans);
}