import sys
input = sys.stdin.readline
t=int(input())
for _ in range(t):
  n,m=map(int,input().split())
  ans=((n*(n+1))//2)%m
  print(ans)