def lcs(x, y)
    c = Array.new(x.size + 1){[]}
    (x.size + 1).times { |i| c[i][0] = 0}
    (y.size + 1).times { |j| c[0][j] = 0}
    1.upto(x.size) do |i|
        1.upto(y.size) do |j|
            if x[i - 1] == y[j - 1] then
                c[i][j] = c[i - 1][j - 1] + 1
            else
                c[i][j] = [c[i - 1][j], c[i][j - 1]].max
            end
        end
    end
    # c.each { |e| p e }
    return c[x.size][y.size]
end

q = gets.chomp.to_i
q.times do
    x = gets.chomp.chars
    y = gets.chomp.chars
    puts lcs(x, y)
end

