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;

 
int[][char] memo;
int[][] memo2;
 
void main()
{
    int Q = readln().strip.to!int;
    foreach(i;0..Q)
    {
        memo.clear();
        auto aList = readln().strip;
        auto bList = readln().strip;
        memoWrite(aList, bList);
        writeln(memo);
        writeln(func(aList, bList, 0));
    }
}

int func(string aList, string bList, int lastIndex)
{
    if(aList.length == 0 || bList.length <= lastIndex)
    {
        return 0;
    }
    if(memo2[aList.length-1][lastIndex] != 0)
    {
        return memo2[aList.length-1][lastIndex];
    }
    int maxLen;
    foreach(i, a; enumerate(aList))
    {
        int li = memo[cast(char)a][lastIndex];
        if(li == -1)
            continue;
        maxLen = max(maxLen, func(aList[i+1..$], bList, li+1)+1);
    }
    memo2[aList.length-1][lastIndex] = maxLen;
    return maxLen;
}

void memoWrite(string aList, string bList)
{
    memo2.length = aList.length;
    memo2.each!((ref a)=>a.length = bList.length);
    foreach(a; aList)
    {
        if(a in memo)
        {
            continue;
        }

        int[] m;
        m.length = bList.length;

        int index = -1;
        for(long i = bList.length-1;i >= 0;i--)
        {
            char b = bList[i];
            if(a==b)
            {
                index = cast(int)i;
            }
            m[i] = index;
        }
        memo[a] = m;
    }
}
