import sys
sys.set_int_max_str_digits(4*10**6)
for _ in range(int(input())):
    n,m = map(int,input().split())
    print(n*(n+1)//2%m)