import std.stdio;
import std.algorithm;
import std.string;
import std.conv;

void main() {
    int n = readln.chomp.to!int;

    for (int i = 0; i < n; i++) {
        string X = readln.chomp;
        string Y = readln.chomp;
        lcs(X, Y).writeln;
    }
}

int lcs(string x, string y) {
    int[][] dp = new int[][](y.length + 1, x.length + 1);
    for (int i = 1; i <= y.length; i++) {
        for (int j = 1; j <= x.length; j++) {
            if (x[j - 1] == y[i - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    return dp[$ - 1][$ - 1];
}