def lcs_rec(i, j)
  return 0 if i == 0 || j == 0
  key = "#{i} #{j}"
  unless $known[key] then
    if $x[i-1] == $y[j-1] then
      $known[key] = lcs_rec(i-1, j-1)+1
    else
      a = lcs_rec(i-1, j)
      b = lcs_rec(i, j-1)
      $known[key] = a > b ? a : b
    end
  end
  return $known[key]
end

n = gets.to_i
n.times{
  $known = {}
  $x = gets.chomp.split("")
  $y = gets.chomp.split("")
  puts lcs_rec($x.size, $y.size)
  p $known
}