t=int(input())
for iii in range(t):
  n,m=map(int,input().split())
  print((n*(n+1)//2)%m)