import sys
input = sys.stdin.readline
sys.set_int_max_str_digits(0)

T=int(input())

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