import sys

sys.set_int_max_str_digits(10**7)

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