# frozen_string_literal: true

q = gets.chomp.to_i

def max(a, b)
  a < b ? b : a
end

q.times do
  x = gets.chomp
  y = gets.chomp

  table = Array.new(x.length + 1).map { Array.new(y.length + 1, 0) }

  x_length = x.length
  y_length = y.length

  (0...x_length).each do |i|
    (0...y_length).each do |j|
      table[i + 1][j + 1] = if x[i] == y[j]
                              table[i][j] + 1
                            else
                              max(table[i + 1][j], table[i][j + 1])
                          end
    end
  end
  puts table.last.last
end

