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

int lcs(string x, string y) {
    int m = x.length.to!int, n = y.length.to!int;
    int[][] c = new int[][](m+1, n+1);
    foreach (i; 1 .. m+1) {
        foreach (j; 1 .. n+1) {
            if (x[i-1] == y[j-1]) {
                c[i][j] = c[i-1][j-1] + 1;
            } else {
                c[i][j] = max(c[i-1][j], c[i][j-1]);
            }
        }
    }
    return c[m][n];
}

void main() {
    int q = readln.chomp.to!int;
    foreach (i; 0 .. q) {
        string x = readln.chomp, y = readln.chomp;
        lcs(x, y).writeln;
    }
}
