def lcs(xs, ys)
  memo = []
  memo[0] = []

  xl = xs.size
  yl = ys.size

  for i in 1..xl
    memo[i] = []
    memo[i][0] = 0
  end

  for j in 1..yl
    memo[0] = []
    memo[0][j] = 0
  end

  max = 0
  for i in 1..xl
    for j in 1..yl
      if xs[i] == ys[i]
        memo[i][j] = if memo[i - 1][j - 1].nil? then 1 else memo[i - 1][j - 1] + 1 end
      else
        if memo[i - 1][j] >= memo[i][j - 1]
          memo[i][j] = memo[i - 1][j]
        else
          memo[i][j] = memo[i][j - 1]
        end
      end
      if max < memo[i][j]
        max = memo[i][j]
      end
    end
  end
  max
end


n = STDIN.gets.to_i

n.times.each {
  a = STDIN.gets
  b = STDIN.gets
  xs = a.split("")
  ys = b.split("")

  puts lcs(xs.take(xs.size - 1), ys.take(ys.size - 1))
}