import java.lang.Math.max

fun main(args: Array<String>) = p38()

fun p38() {
    val q = readLine()!!.toInt()

    val answer = StringBuilder()

    repeat(q) {
        val x = readLine()!!
        val y = readLine()!!

        val dp = Array(x.length + 1) { IntArray(y.length + 1) }

        for ((xi, xc) in x.withIndex()) {
            for ((yi, yc) in y.withIndex()) {
                dp[xi + 1][yi + 1] = (if (xc == yc) dp[xi][yi] + 1 else max(dp[xi + 1][yi], dp[xi][yi + 1]))
            }
        }

        answer.appendln(dp.last().last())
    }

    print(answer)
}

