fun main(args: Array<String>) {
    val MAX = 1000
    var N = Integer.parseInt(readLine());
    var L = Array(MAX+1) { _ -> IntArray(MAX+1) };
    
    for (x in 1..N) {
        val a = readLine();
        val b = readLine();
        
        val n = a!!.length;
        val m = b!!.length;
        
        for (i in 0..(n-1)) {
            for (j in 0..(m-1)) {
                if (a[i] == b[j]) {
                    L[i+1][j+1] = L[i][j] + 1
                } else {
                    L[i+1][j+1] = if (L[i+1][j] > L[i][j+1]) {
                        L[i+1][j]
                    } else {
                        L[i][j+1]
                    }
                }
            }
        }
        println(L[n][m]);
    }
}

