#include <bits/stdc++.h>
using namespace std;
int main() {
  int number;
  string x;
  string y;
  int L[1001][1001];
  cin >> number;
  while (cin >> x >> y) {
    int x_length = x.length();
    int y_length = y.length();
    for (int i = 0; i <= x_length; i++) L[i][0] = 0;
    for (int j = 0; j <= y_length; j++) L[0][j] = 0;
    for (int i = 1; i <= x_length; i++) {
      for (int j = 1; j <= y_length; j++) {
        if (x[i - 1] == y[j - 1])
          L[i][j] = 1 + L[i - 1][j - 1];
        else
          L[i][j] = max(L[i][j - 1], L[i - 1][j]);
      }
    }
    cout << L[x_length][y_length] << endl;
  }
}
