class LongestCommon
  attr_accessor :c

  N = 1000

  def initialize(x, y)
    @x = x
    @y = y
    @c = Array.new(N+1).map { Array.new(N+1, nil) }
    (1..x.size - 1).each { |i| @c[i][0] = 0 }
    (1..y.size - 1).each { |j| @c[0][j] = 0 }
    @c[0][0] = 0
  end

  def lcs
    max = 0
    (1..@x.size - 1).each do |i|
      (1..@y.size - 1).each do |j|
        if @x[i] == @y[j]
          @c[i][j] = @c[i-1][j-1] + 1
        else
          @c[i][j] = [@c[i][j-1], @c[i-1][j]].max
        end
        max = @c[i][j] if @c[i][j] > max
      end
    end
    return max
  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
end