#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007

int main() {
  
 int q;
 cin >> q;

 for(int i = 0;i < q;i++) {
   string X,Y;
   cin >> X >> Y;
   int x = X.size(),y = Y.size();

   int dp[x+1][y+1];
   for(int i = 0;i <= x;i++) {
     dp[i][0] = 0;
   }
   for(int i = 0;i <= y;i++) {
     dp[0][i] = 0;
   }

   for(int i = 1;i<=x;i++) {
     for(int j = 1;j <= y;j++) {
       if(X.at(i-1) == Y.at(j-1)) 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][y] << endl;

 }

  
}



