class SequencePair
  @@lcs_table = Array.new(1001).map{Array.new(1001,0)}

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

q = STDIN.gets.to_i

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