$memo = []
$memo[0, 0] = 0

def lcs(xs, ys)
  xl = xs.size
  yl = ys.size

  if xl == 0 || yl == 0
    0
  elsif xs.last == ys.last
    if $memo[xl].nil?
      $memo[xl] = []
    end

    a = $memo[xl][yl]
    if a.nil?
      a = lcs(xs.take(xl - 1), ys.take(yl - 1)) + 1
      $memo[xl][yl] = a
    end
    a

  else
    if $memo[xl].nil?
      $memo[xl] = []
    end

    yi = ys.size - 1
    a = if $memo[xl] != nil then $memo[xl][yi] else nil end
    if a.nil?
      a = lcs(xs, ys.take(yi))
    end

    xi = xs.size - 1
    b = if $memo[xi] != nil then $memo[xi][yl] else nil end
    if b.nil?
      b = lcs(xs.take(xi), ys)
    end
    if a > b
      $memo[xl][yl] = a
      a
    else
      $memo[xl][yl] = b
      b
    end
  end
end


n = STDIN.gets.to_i

n.times.each {
  a = STDIN.gets
  b = STDIN.gets
  xs = []
  ys = []
  if a.size < b.size
    xs = a.split("")
    ys = b.split("")
  else
    xs = b.split("")
    ys = a.split("")
  end
  puts lcs(xs.take(xs.size - 1), ys.take(ys.size - 1))
}