def lcs(x, y)
  c = Array.new(y.length + 1, 0)
  x.each_char do |xi|
    tmp = c.dup
    y.each_char.with_index do |y, ji|
      j = ji + 1
      if xi == y
        c[j] = tmp[j - 1] + 1
      elsif c[j] < c[j - 1]
        c[j] = c[j - 1]
      end
    end
  end
  c[-1] - 1
end
 
 
n = gets.chomp.to_i
 
n.times.each do |i|
  x = gets
  y = gets
  puts lcs(x, y)
end