def LCS(array1, array2)
  array_i = array1.length
  array_j = array2.length
  array = Array.new(array_i+1).map{Array.new(array_j+1,0)}

  1.upto array_i do |i|
    1.upto array_j do |j|
      array[i][j] = (array1[i-1] == array2[j-1]) ? array[i][j] = array[i-1][j-1] + 1 : ((array[i][j-1] > array[i-1][j]) ? array[i][j-1] : array[i-1][j] )
    end
  end
  array.last.last
end

q = gets.to_i
q.times do
  array1 = gets.chomp.split("")
  array2 = gets.chomp.split("")
  puts LCS(array1, array2)
end

