# lcs.rb
q = STDIN.gets.split[0].to_i
q.times {
  c=Array.new(1002){Array.new(1002)}
  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
      #printf("%d %d %s %s|",i,j,x[i],y[j])
      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
  end

  puts c[lx][ly]
}