# lcs.rb
q = STDIN.gets.split[0].to_i
c=Array.new(1002,Array.new(1002))
q.times {
  x = STDIN.gets.split[0]
  y = STDIN.gets.split[0]
  lx = x.length
  ly = y.length


  0.upto(ly) {|i| c[0][i]=0}
  0.upto(lx) {|i| c[i][0]=0}
  max_=0
  for i in 0...lx do 
    for j in 0...ly do
      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

    end
     if max_ < c[i+1][j+1] then
       max_ = c[i+1][j+1]
     end
  end
  puts max_
}