T=int(input())
for i in range(T):
    N,M=map(int,input().split())
    #print(N,M)
    #print(M)
    F=N+1
    if N&1:
        F//=2
    else :
        N//=2
    N%=M
    F%=M
    print((N*F)%M)