def get_lcs s1, s2
  s1 = s1.chars
  s2 = s2.chars
  l1 = s1.length
  l2 = s2.length
  dp = Array.new(l1 + 1){Array.new(l2 + 1)}
  0.upto(l1) do |i|
    0.upto(l2) do |j|
      dp[i][j] = if i == 0 || j == 0
                   0
                 elsif s1[i - 1] == s2[j - 1]
                   dp[i - 1][j - 1] + 1
                 else
                   [dp[i][j - 1], dp[i - 1][j]].max
                 end
    end
  end
  dp[l1][l2]
end

n = gets.chomp.to_i
while seq_1 = gets
  seq_1 = seq_1.chomp
  seq_2 = gets.chomp
  puts get_lcs(seq_1, seq_2)
end
