def lcs(string1, string2)
	# 扱いやすさの為に1オリジンで扱えるようにする
	string1 = " " + string1
	string2 = " " + string2

	# 部分的なlcsの結果を格納する表を作る
	# partial_lcs[i][j]はstring1[0..i]とstring2[0..j]のlcsになる
	partial_lcs = Array.new(string1.length) { Array.new(string2.length, 0) }
	1.upto(string1.length - 1) do |i|
		1.upto(string2.length - 1) do |j|

			if string1[i] == string2[j]
				partial_lcs[i][j] = partial_lcs[i - 1][j - 1] + 1

			elsif partial_lcs[i - 1][j] >= partial_lcs[i][j - 1]
				partial_lcs[i][j] = partial_lcs[i - 1][j]

			else
				partial_lcs[i][j] = partial_lcs[i][j - 1]

			end

		end
	end
	partial_lcs[-1][-1] # 表の一番右下、つまり全体のlcs
end

n = STDIN.gets.to_i
n.times do
	string1 = STDIN.gets.chomp!
	string2 = STDIN.gets.chomp!
	puts lcs(string1, string2)
end