#include<iostream>

#include<stdlib.h>

#include<string.h>

using namespace std;

char s1[100],s2[100];

typedef struct BiTNode

{

	char data;

	struct BiTNode *lchild,*rchild;

}BiTNode,*BiTree;

void build(BiTree &T,char *s1,char *s2,int n)

{

	if(n<=0)  T=NULL;

	else

	{

		int p=strchr(s1,s2[n-1])-s1;//查找头结点在S1中的位置.

		T=new BiTNode;

		T->data=s2[n-1];

		build(T->lchild,s1,s2,p);//创建左子树

		build(T->rchild,s1+p+1,s2+p,n-p-1);//创建右子树

	}

}

int high_tree(BiTree T)

{

	int h,left,right;

	if(!T)

	{  return 0;}

	else

	{

		left=high_tree(T->lchild);

		right=high_tree(T->rchild);

		h=((left>right?left:right)+1);

		return h;

	}

}

int main()

{

	int n,len,m;

	BiTree T;

	cin>>n;

	while(n--)

	{

		cin>>s1>>s2;

		len= strlen(s1);

		build(T,s1,s2,len);

		m=high_tree(T);

		cout<<m<<endl;

	}

	return 0;

}