#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX(a,b) a > b ? a : b
int main()
{
    int n;
    scanf("%d",&n);
    while (n--)
    {
        char a[1000] = {0}, b[1000] = {0};
        scanf("%s%s",a,b);
        int a_len = strlen(a), b_len = strlen(b);
        int dp[a_len+1][b_len+1];      //定义dp[][]用来记录所有可能的最长公共子序列长度
        memset(dp, 0, sizeof(dp));    //初始化二维数组dp[][];
        int i, j;
        for (i = 1; i <= a_len; i++)    //注意i和j应该从一开始
        {
            for (j = 1; j <= b_len; j++)
            {
                // 如果a[i-1] == b[i-1],则最长公共子序列长度加1
                if (a[i-1] == b[j-1])
                    dp[i][j] = dp[i-1][j-1] + 1;

                //如果a[i-1] == b[i-1],则在两个子问题中去较大值
                else
                    dp[i][j] = MAX(dp[i-1][j], dp[i][j-1]);
            }
        }
        printf("%d\n",dp[a_len][b_len]);
    }
    return 0;
}