N = gets.to_i
N.times{
  x = gets.chomp
  y = gets.chomp
  xs = x.size
  ys = y.size
  m = Array.new(ys+1, 0)
  (1..xs).each{|xi|
    pre = 0
    a = [0]
    (1..ys).each{|yi|
      if x[xi-1] == y[yi-1]
        pre = m[yi-1] + 1
      else
        pre = [m[yi], pre].max
      end
      a << pre
    }
    m = a
  }
  puts m[-1]
}