def f(str1, str2, it1, arr)
  #p [str1, str2, it1, arr]
  result = Array.new(arr.size)
  result[0] = it1
  str2[1..-1].each_with_index{|i, idx|
    if str1[it1] == i
      result[idx + 1] = arr[idx]
    else
      result[idx + 1] = arr[idx + 1] > result[idx] ? result[idx] + 1 : arr[idx +  1] + 1
    end
  }
  if it1 != str1.size - 1
    f(str1, str2, it1 + 1, result)
  else
    #p result[-1]
    return result[-1]
  end
end
def lgs(str1, str2)
  return ((str1.size + str2.size) - f([" "] + str1.split(//), [" "] + str2.split(//), 1, Array.new(str2.size + 1){|i|i})) / 2
end
def main(input = STDIN)
  input.gets.to_i.times do
    puts lgs(input.gets.chomp, input.gets.chomp)
  end
end
main

