n = gets.to_i
a = []
n.times{
  # x = "defacf".chars
  # y = "dfc".chars
  x = gets.chomp
  y = gets.chomp
  a << [x,y]
}

def lcs(a)
  a.each do |i|
    x = i[0].chars
    y = i[1].chars 
    m = x.length
    n = y.length
    c = Array.new(m+1).map{Array.new(n+1,0)}
    for i in 0..m-1
      for j in 0..n-1
        if x[i] == y[j]
          c[i+1][j+1] = c[i][j] + 1
        elsif c[i][j+1] >= c[i+1][j]
          c[i+1][j+1] = c[i][j+1]
        else
          c[i+1][j+1] = c[i+1][j]
        end
        # p c
      end
    end
    puts c[-1][-1]
  end
end

lcs(a)