#include<iostream>
using namespace std;
string x,y;
int q;

int lcs(){
  int c[1002][1002],ans=0;
  int  m=(int)x.size(),n=(int)y.size();
    x=' '+x,y=' '+y;
  for(int i=1;i<=m;i++)c[i][0]=0;
  for(int i=1;i<=n;i++)c[0][i]=0;
  for(int i=1;i<=m;i++)
    for(int j=1;j<=n;j++){
      if(x[i]==y[j])c[i][j]=c[i-1][j-1]+1;
      else if(c[i-1][j]>=c[i][j-1])c[i][j]=c[i-1][j];
      else c[i][j]=c[i][j-1];
      if(ans<=c[i][j])ans=c[i][j];
    }
  return ans;
}

int main(){
  cin>>q;
  for(int i=0;i<q;i++){
    cin>>x>>y;
  cout<<lcs()<<endl;
  }
  return 0;
}