fun main(args: Array<String>) {
    repeat(readLine()?.toInt() ?: 0) {
        val str1 = readLine() ?: ""
        val str2 = readLine() ?: ""
        val matrix = Array(str1.length + 1) {
            IntArray(str2.length + 1)
        }
        for (i in 0 until str1.length) {
            matrix[i][0] = 0
        }
        for (j in 0 until str2.length) {
            matrix[0][j] = 0
        }
        for (i in str1.indices) {
            for (j in str2.indices) {
                matrix[i + 1][j + 1] = if (str1[i] == str2[j]) {
                    matrix[i][j] + 1
                } else if (matrix[i][j + 1] >= matrix[i + 1][j]) {
                    matrix[i][j + 1]
                } else {
                    matrix[i + 1][j]
                }
            }
        }
        println(matrix.flatMap { it.toList() }.max())
    }
}
