# gets.chomp.to_i
# gets.chomp.split(" ").map(&:to_i)
# gets.chomp.split(" ").map{|x| x.to_i}

t = gets.chomp.to_i
#results = []
len = Array.new(1001){ Array.new(1001, 0) }
for dataset in 0...t
  a = gets.chomp.split(//)
  b = gets.chomp.split(//)

  # len = Array.new(a.length()+1, Array.new(b.length()+1, 0)) # wrong expression
  for ia in 1..a.length()
    for ib in 1..b.length()
      if a[ia-1] == b[ib-1]
        len[ia][ib] = len[ia-1][ib-1]+1
      else
        len[ia][ib] = [len[ia][ib-1], len[ia-1][ib]].max
      end
    end
  end
  #results.push(len[a.length()][b.length()])
  puts len[a.length()][b.length()]
end

#for i in 0...t
#  puts results[i]
#end