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