MAX_LEN = 1000
dp = Array.new (MAX_LEN + 1) { Array.new MAX_LEN + 1 }
gets.to_i.times do
  x, y = gets.chomp.chars, gets.chomp.chars
  m, n = x.size, y.size
  for i in 0..m
    dp[i][0] = 0
  end
  for j in 0..n
    dp[0][j] = 0
  end
  for i in 1..m
    for j in 1..n
      a, b = dp[i-1][j], dp[i][j-1]
      dp[i][j] = (a > b ? a : b)
      if x[i-1] == y[j-1]
        c = dp[i-1][j-1] + 1
        dp[i][j] = c if dp[i][j] < c
      end
    end
  end
  p dp[m][n]
end