$t_lcs = []

def calc_lcs(str_x, str_y, i_x, i_y)
  return $t_lcs[i_x][i_y] if $t_lcs[i_x][i_y] >= 0

  if (str_x[i_x] == str_y[i_y]) then
    pre_lcs = calc_lcs(str_x, str_y, i_x-1, i_y-1)
    lcs = pre_lcs + 1
  else
    pre_lcs1 = calc_lcs(str_x, str_y, i_x-1, i_y)
    pre_lcs2 = calc_lcs(str_x, str_y, i_x, i_y-1)
    lcs = [pre_lcs1, pre_lcs2].max
  end

  $t_lcs[i_x][i_y] = lcs
  return $t_lcs[i_x][i_y]
end

def setup_table(str_x, str_y)
  $t_lcs.clear

  (str_x.length+1).times do 
    cols = []
    (str_y.length+1).times do
      cols << -1
    end
    $t_lcs << cols
  end

  x_ch = str_x[1]
  y_ch = str_y[1]
  $t_lcs.each_with_index do |row, index|
    part_y = str_y[0..index]
    row[1] = (part_y.include?(x_ch)) ? 1 : 0
  end
  $t_lcs[1].each_with_index do |col, index|
    next if index == 0
    part_x = str_x[0..index]
    $t_lcs[1][index] = (part_x.include?(y_ch)) ? 1 : 0
  end
end

def print_table
  $t_lcs.each do |row|
    row.each do |col|
      printf "%3d", col
    end
    puts ""
  end
end


# main
n = gets.chomp.to_i
(n).times do 
  str_x = gets.chomp
  str_y = gets.chomp
  setup_table(str_x, str_y)
  puts calc_lcs(" "+str_x, " "+str_y, str_x.length, str_y.length)
end