def lcs(x, y)
  xn = x.size
  yn = y.size
  m = Array.new(yn+1){0}
  xn.times{|i|
    tmp = m.clone
    yn.times{|j|
      k = j+1
      if x[i] == y[j] then
        m[k] = tmp[j] + 1
      elsif m[k] < m[j]
        m[k] = m[j]
      end
    }
  }
  return m[-1]
end

n = gets.to_i
n.times{
  x = gets.chomp.split("")
  y = gets.chomp.split("")
  puts lcs(x, y)
}