import sys
input = sys.stdin.readline

sys.set_int_max_str_digits(10**7)

T=int(input())
for tests in range(T):
    N,M=map(int,input().split())

    print((N*(N+1)//2)%M)