require "big"

read_line.to_i.times do
  puts solve()
end

def solve
  n, m = read_line.split.map { |v| BigInt.new(v) }
  n %= m
  return n * (n + 1) // 2 % m
end