require "big"

read_line.to_i.times do
  puts solve()
end

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