import sys;sys.set_int_max_str_digits(0)
for _ in range(int(input())):
  n,m=map(int,input().split())
  n1=n%m
  n2=(n+1)%m
  s=(n1*n2//2)%m
  print(s)