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