import sys
sys.set_int_max_str_digits(0)
t = int(input())
for ti in range(t):
    x,m = map(int,input().split())
    y = x+1
    if x%2==0:
        x //= 2
    else:
        y //= 2
    x %= m
    y %= m
    print((x*y)%m)