import sys

sys.set_int_max_str_digits(10**7)


def solve():
    n, m = map(int, input().split())
    if n < m:
        print(n * (n + 1) // 2 % m)
        return
    n %= m
    n += m
    print(n * (n + 1) // 2 % m)


for _ in range(int(input())):
    solve()