#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define len(str) (int)(str.length())
int main() {
	int N;
	cin >> N;

	for (int a = 0; a < N; a++)
	{
		string X, Y;
		cin >> X >> Y;
		vector<vector<int> > dp(len(X) + 1, vector<int>(len(Y) + 1, 0));
		for (int a = 1; a <= len(X); a++)
		{
			for (int b = 1; b <= len(Y); b++)
			{
				if (X[a - 1] == Y[b - 1]) {
					dp[a][b] = dp[a - 1][b - 1] + 1;
				}
				else {
					dp[a][b] = max(dp[a - 1][b], dp[a][b - 1]);
				}
			}
		}
		cout << dp[len(X)][len(Y)] << endl;
	}
}
