def lcs(x, y)
  xn = x.size
  yn = y.size
  m = Array.new(xn+1){Array.new(yn+1){0}}
  0.upto(xn){|i|
    m[i][0] = 0
  }
  0.upto(yn){|j|
    m[0][j] = 0
  }
  1.upto(xn){|i|
    1.upto(yn){|j|
      if x[i-1] == y[j-1] then
        m[i][j] = m[i-1][j-1]+1
      else
        m[i][j] = (m[i-1][j] > m[i][j-1] ? m[i-1][j] : m[i][j-1])
      end
    }
  }
  return m[xn][yn]
end

n = gets.to_i
n.times{
  x = gets.chomp.split("")
  y = gets.chomp.split("")
  puts lcs(x, y)
}