T = int(input())

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