# 純粋な再帰だとスタックが深くなりすぎるので、グローバル変数に格納する.
# $lcsList は二重配列で、$lcsList[i][j]は
# 文字列の長さがそれぞれi, jであることを表す.
$lcsList = []

def lcs(x, y)
  i = x.length-1
  j = y.length-1
  l = 0

  if $lcsList[i][j] != -1 # すでに求めてある
    return $lcsList[i][j]
  elsif i == 0 # xの要素が一つ
    l = y.include?(x[0]) ? 1 : 0
  elsif j == 0 # yの要素が一つ
    l = x.include?(y[0]) ? 1 : 0  
  elsif x[i] == y[j]      # 最後の要素が等しい
    l = lcs(x[0..-2], y[0..-2]) + 1
  else
    l = [lcs(x[0..-2], y), lcs(x, y[0..-2])].max
  end

  $lcsList[i][j] = l
end

def solveLCS()
  strX = gets.chomp
  strY = gets.chomp
  $lcsList = Array.new(strX.length).map{ Array.new(strY.length, -1) }
  lcs(strX, strY)
  max = 0
  $lcsList.each do |list|
    max = list.max if max < list.max
  end
  return max
end

if __FILE__ == $0
  gets.to_i.times do
    puts solveLCS.to_s
  end
end