#include
#include
#include
char zhongxu[100];
char houxu[100];
struct node
{
char data;
struct node *l,*r;
}*T,*TT;
int treedepth(struct node *TT)
{
int i,j;
if(!TT) return 0;
i=treedepth(TT->l);
j=treedepth(TT->r);
return i>j?i+1:j+1;
}
struct node * creattree(char *zs,char *hs,int l)
{
//struct node *T;
T=(struct node *)malloc(sizeof(struct node));
if(l==0) return 0;
T->data=hs[l-1];
// printf("%c\n",T->data);
int i=0;
for(;i<=l-1;i++)
{
if(zs[i]==hs[l-1]) break;
}
T->l=creattree(zs,hs,i);
T->r=creattree(zs+i+1,hs+i,l-i-1);
return T;
}
int main()
{
int t,len;
scanf("%d",&t);
while(t--)
{
struct node *TT;
scanf("%s%s",zhongxu,houxu);
len=strlen(zhongxu);
TT=creattree(zhongxu,houxu,len);
printf("%d\n",treedepth(TT));
zhongxu[0]='\0';
houxu[0]='\0';
}
}