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*pow(2,-1,m)
  print(s%m)