#include <iostream>

int lcs(std::string x, std::string y, int m, int n)
{
    int l[m+3][n+3];
    for(int i = 0; i <= m; i++)
        l[i][0] = 0;
    for(int j = 0; j <= n; j++)
        l[0][j] = 0;
    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= n; j++)
        {
            if(x[i] == y[j]) l[i][j] = l[i-1][j-1] + 1;
            else l[i][j] = (l[i][j-1] > l[i-1][j] ? l[i][j-1] : l[i-1][j]);
        }
    return l[m][n];
}

int main() {
    int t;
    std::cin>>t;
    std::string a,b;
    int m,n;
    for(int i = 0; i < t; i++)
    {
        std::cin>>m>>a>>n>>b;
        std::cout<<lcs(a,b,m,n)<<"\n";
    }
    return 0;
}