class SequencePair

  def initialize(seq1, seq2)
    @seq1 = seq1.chomp
    @seq2 = seq2.chomp
    @lcs_table = Array.new(seq1.length+1).map{Array.new(seq2.length+1,0)}
  end

  def lcs_len
    if @seq1.length*@seq2.length==0
      return 0
    elsif @seq1==@seq2
      return @seq1.length
    else
      1.upto(@seq1.length) do |i|
        1.upto(@seq2.length) do |j|
          if @seq1[i-1]==@seq2[j-1]
            match=1
          else
            match=0
          end
          @lcs_table[i][j] = [ @lcs_table[i-1][j-1] + match, @lcs_table[i-1][j], @lcs_table[i][j-1] ].max
        end
      end
      return @lcs_table[@seq1.length][@seq2.length]
    end
  end
end

q = STDIN.gets.to_i

q.times do
  seq1 = STDIN.gets
  seq2 = STDIN.gets
  seq_pair=SequencePair.new(seq1,seq2) 
  print "#{seq_pair.lcs_len}\n"
end