def compare(x,y)
   l = Array.new(x.length + 1) {Array.new(y.length + 1, 0)}
   1.upto(x.length) do |i|
      1.upto(y.length) do |j|
         l[i][j]= if x[i-1] == y[j-1]
            l[i-1][j-1]+1
         else
            a,b=l[i][j-1],l[i-1][j]
            (a > b) ? a : b
         end
      end
   end
   puts l[x.length][y.length]
end

num=gets.to_i

x=Array.new
y=Array.new
cnt=Array.new

num.times do
   x.push(gets.chomp!)
   y.push(gets.chomp!)
end

x.zip(y) do |x, y|
 compare(x,y)
end
