
t = gets.chomp.to_i
len = Array.new(1001){ Array.new(1001, 0) }
for dataset in 0...t
  a = gets.chomp
  b = gets.chomp
  for ia in 1..a.length()
    for ib in 1..b.length()
      if a[ia-1] == b[ib-1]
        len[ia][ib] = len[ia-1][ib-1]+1
      else
        len[ia][ib] = [len[ia][ib-1], len[ia-1][ib]].max
      end
    end
  end
  puts len[a.length()][b.length()]
end