class LongestCommon
  attr_accessor :c

  def initialize(x, y)
    @x = x
    @y = y
    @c = Array.new(x.size).map{ Array.new(y.size, nil) }
  end

  def lcs(i, j)
    return @c[i][j] = 0 if i == 0 || j == 0
    return @c[i][j] if @c[i][j]
    if @x[i] == @y[j]
      return @c[i][j] = lcs(i-1, j-1) + 1
    else
      return @c[i][j] = [lcs(i, j-1), lcs(i-1, j)].max
    end
  end
end

n = gets.to_i
n.times do |i|
  x = gets.strip.chars.to_a.unshift nil
  y = gets.strip.chars.to_a.unshift nil
  lc = LongestCommon.new(x, y)
  puts lc.lcs(x.size - 1, y.size - 1)
end