function Main(input){
    input = input.split("\n");
    var q = parseInt(input[0],10);

    var dp = new Array(1001);
    for(var i = 0;i <= 1000;i++)
        dp[i] = new Array(1001);

    for(var k = 1;k <= q;k++){
        var x = "0"  + input[k * 2 - 1];
        var y = "1" + input[k * 2];
        
        for(var i = 0;i < x.length;i++)
            dp[0][i] = 0;

        for(var i = 0;i < y.length;i++)
            dp[i][0] = 0;

        for(var i = 1;i < y.length;i++){
            for(var j = 1;j < x.length;j++){
                if(y[i] != x[j])
                    dp[i][j] = Math.max(dp[i - 1][j],dp[i][j - 1]);
                else
                    dp[i][j] = Math.max(dp[i - 1][j - 1] + 1,dp[i - 1][j],dp[i][j - 1]);
            }
        }
        console.log(dp[y.length - 1][x.length - 1]);
    }
}
Main(require("fs").readFileSync("/dev/stdin","utf8"));