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