

def max a, b
	a > b ? a : b
end

def lcs c1, c2, dp, n, m
	m = c1.length
	n = c2.length
	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] = max dp[i - 1][j], dp[i][j - 1]
			end
			maxl = max dp[i][j], maxl
		end
	end
	return maxl
end

n = gets.to_i
n.times do
	c1 = gets.chomp!.split("").map(&:to_s)
	c2 = gets.chomp!.split("").map(&:to_s)
	n = c1.length
	m = c2.length
	dp = Array.new(n + 1){Array.new(m + 1){0}}
	puts lcs(c1, c2, dp, n, m)
end