import sys
sys.set_int_max_str_digits(4000010)

for _ in range(int(input())):
    n, m = map(int, input().split())
    n %= m
    print(((n+1)*n//2)%m)