def lcs c1, c2
	dp = Array.new(c2.length + 1){0}
	c1.each_char do |ch1|
		tmp = dp.dup
		c2.each_char.each_with_index do |ch2, ji|
			j = ji + 1
			if ch1 == ch2
				dp[j] = tmp[j - 1] + 1
			elsif  dp[j] < dp[j - 1] 
				dp[j] = dp[j - 1]
			end
		end
	end
	return dp[-1]
end

n = gets.to_i
dp = Array.new(1001){0}

n.times do
	c1 = gets.chomp
	c2 = gets.chomp


	puts lcs(c1, c2)
end