#include<iostream>
#include<string>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAX=1005;
int dp[MAX][MAX]={0};
int main(){
	string x,y;
	int q;
	cin>>q;
	while(q--){
		cin>>x>>y;
		memset(dp,0,sizeof(dp));
		x=" "+x;y=" "+y;
		for(int i=1;i<x.length();i++){
			for(int j=1;j<y.length();j++){
				if(x[i]==y[j])dp[i][j]=dp[i-1][j-1]+1;
				else {
					dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
				}
			}
		}
		cout<<dp[x.length()-1][y.length()-1]<<endl;
	}
	return 0;
}
