def longestCommonSubsequence(x,y,i,j)
  if (i < 0 || j < 0)
    return 0
  elsif (x[i] == y[j])
    return longestCommonSubsequence(x,y,i-1, j-1) + 1
  else
    if longestCommonSubsequence(x,y, i-1,j) < longestCommonSubsequence(x, y, i,j-1)
      return longestCommonSubsequence(x, y, i, j-1)
    else
      return longestCommonSubsequence(x,y, i-1,j)
    end
  end
end

n = gets.to_i
n.times do
  x = gets
  y = gets
  puts longestCommonSubsequence(x,y,x.length-2,y.length-2)
end