import sys
sys.set_int_max_str_digits(0)
T=int(input())
for _ in range(T):
    N,M=map(int,input().split())
    print((1+N)*N//2%M)