N = 1000

def max(x, y)
	return x > y ? x : y
end

def lcs(x, y)
	m = x.size
	n = y.size
	maxl = 0
	x = ' ' + x
	y = ' ' + y

	c = Array.new(N + 1).map{Array.new(N + 1, 0)}

	for i in 1..m do
		c[i][0] = 0
	end
	for j in 1..n do
		c[0][j] = 0
	end

	for i in 1..m do
		for j in 1..n do
			if x[i] == y[j]
				c[i][j] = c[i - 1][j - 1] + 1
			else
				c[i][j] = max(c[i - 1][j], c[i][j - 1])
			end
			maxl = max(maxl, c[i][j])
		end
	end

	return maxl
end

n = gets.to_i
n.times do
	s1 = gets.chomp
	s2 = gets.chomp
	puts lcs(s1, s2)
end