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

n = gets.to_i
n.times do
  x = gets
  y = gets
  a = Array.new(x.length-1) { Array.new(y.length-1,0)}
  puts longestCommonSubsequence(x,y,x.length-2,y.length-2, a)
end