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