def get_lcs(master, slave)
  # NOTE: result[cs_length] = end_position
  slave.each_char.reduce([-1]) do |result, new_char|
    new_result = result.dup
    rest_result = result.each_with_index.to_a
    master.each_char.with_index.find_all { |c, _| c == new_char }
      .each do |_, new_pos|
        taken = rest_result.take_while { |pos, _| new_pos > pos }
        if taken.any?
          _, use_cs_length = taken.last
          new_result[use_cs_length + 1] = new_pos
          rest_result = rest_result[taken.length..-1]
        end
      end
    new_result
  end.length - 1
end

n = gets.chomp.to_i
n.times do
  master = gets.chomp
  slave = gets.chomp
  puts get_lcs(master, slave)
end

