import sys
sys.set_int_max_str_digits(4000004)

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