import std.array, std.stdio, std.conv, std.string, std.math, std.random, std.range,std.functional, std.typecons;
import std.algorithm.searching, std.algorithm.sorting, std.algorithm.iteration, std.algorithm.comparison;
 
void main()
{
    int Q = readln().strip.to!int;
    foreach(i;0..Q)
    {
        auto aList = readln().strip;
        auto bList = readln().strip;
        writeln(lcs(aList, bList));
    }
}

int lcs(string aList, string bList)
{
    int[][] memo;
    memo.length = bList.length+1;
    memo[0].length = aList.length+1;
    foreach(i; 1..aList.length+1)
    {
        memo[i].length = aList.length+1;
        char a = aList[i-1];
        foreach(j; 1..bList.length+1)
        {
            char b = bList[j-1];
            if(a==b)
            {
                memo[i][j] = memo[i-1][j-1]+1;
            }else{
                memo[i][j] = max(
                    memo[i-1][j],
                    memo[i][j-1],
                );
            }
        }
    }
    return memo[aList.length][bList.length];
}
