for q in range(int(input())):
  a,b=map(int,input().split())
  if a%2==0:
    print(int((1+a)*(a//2))%b)
  else:
    print(int((1+a)*(a//2)+((a+1)//2))%b)