n = gets.to_i

def lcs_x(xs, ys, bef)
    ys_all = Array.new(ys)
    if xs == []
        return bef.last
    else
        x    = xs.shift
        memo = lcs_y(x, ys, bef, [0])
        lcs_x(xs, ys_all, memo)
    end
end

def lcs_y(x, ys, bef, memo)
    if ys == []
        return memo
    elsif x == ys[0]
        memo << bef[0] + 1
    else
        memo << [bef[1], memo.last].max
    end
    ys.shift; bef.shift
    lcs_y(x, ys, bef, memo)
end

n.times do
    xs = gets.chomp.split("")
    ys = gets.chomp.split("")
    bef = Array.new(ys.size + 1) {0}
    p lcs_x(xs, ys, bef)
end
