import sys;sys.set_int_max_str_digits(0)
for _ in range(int(input())):
  n,m=map(int,input().split())
  if n%2:
    n1=n%m
    n2=(n+1)//2%m
  else:
    n1=n//2%m
    n2=(n+1)%m
  print(n1*n2%m)