object Main {
    def main(args: Array[String]): Unit = {
        val n = readInt;
        for (i <- (0 until n)) {
            println(lcs(readLine, readLine));
        }
    }

    def lcs(a: String, b: String): Int = {
        val lenA = a.length;
        val lenB = b.length;
        val matrix = Array.ofDim[Int](lenA + 1, lenB + 1);
        for (y <- (1 to lenA); x <- (1 to lenB)) {matrix(y)(x) = -1;}
        def _lcs(y: Int, x: Int): Int = {
            if (matrix(y)(x) == -1) {
                val lcs1 = _lcs(y - 1, x - 1);
                val lcs2 = _lcs(y, x - 1);
                val lcs3 = _lcs(y - 1, x);
                if (a(y - 1) == b(x - 1)) {
                    matrix(y)(x) = max(lcs1 + 1, lcs2, lcs3);
                } else {
                    matrix(y)(x) = max(lcs1, lcs2, lcs3);
                }
            }
            matrix(y)(x)
        }
        _lcs(lenA, lenB);
    }

    def max(a: Int, b: Int, c: Int): Int = {
        if (b > c) {
            if (a > b) a else b;
        } else {
            if (a > c) a else c;
        }
    }
}
