read_line.to_i.times do
  puts solve()
end

def solve
  ns, ms = read_line.split
  m = ms.to_i
  n = 0i64
  ns.chars.each do |ch|
    n = (n * 10 + ch.to_i) % m
  end
  return n * (n + 1) // 2 % m
end