
def lcs c1, c2, dp, n, m
	c1.insert(0, " ")
	c2.insert(0, " ")
	maxl = 0
	1.upto m do |i|
		1.upto n do |j|
			if c1[i] == c2[j]
				dp[i][j] = dp[i - 1][j - 1] + 1
			else
				dp[i][j] = dp[i - 1][j] > dp[i][j - 1] ? dp[i - 1][j] : dp[i][j - 1]
			end
			maxl =  dp[i][j] > maxl ? dp[i][j] : maxl
		end
	end
	return maxl
end

n = gets.to_i
dp = Array.new(1001){Array.new(1001){0}}
n.times do
	c1 = gets.chomp!.split("")
	c2 = gets.chomp!.split("")
	l = c1.size
	m = c2.size

	puts lcs(c1, c2, dp.dup, l, m)
end