import sys

rl = sys.stdin.readline
sys.set_int_max_str_digits(0)
t = int(rl())

for _ in range(t):
    n, m = map(int, rl().split())
    n_1 = n + 1
    if n % 2 == 0:
        n //= 2
    else:
        n_1 //= 2
    n %= m
    n_1 %= m
    print(n * n_1 % m)