
count = gets.chomp.to_i
ans = []
def lcs(val1, val2, ans)
  m = val1.length
  n = val2.length
  array = Array.new(m+1, Array.new(n+1, 0))
  maxl = 0

  ind1 = 1
  while ind1 <= m do
    ind2 = 1
    while ind2 <= n do
      if val1[ind1] == val2[ind2]
        array[ind1][ind2] = array[ind1-1][ind2-1] + 1
      else
        array[ind1][ind2] = [array[ind1-1][ind2], array[ind1][ind2-1]].max
      end
      maxl = [maxl, array[ind1][ind2]].max
      ind2 += 1
    end
    ind1 += 1
  end

  ans << maxl
end

count.times do
  val1 = gets.chomp
  val2 = gets.chomp
  lcs(val1, val2, ans)
end

puts ans