t = int(input())

for i in range(t):
    n, m = map(int, input().split())

    print(n * (n + 1) // 2 % m)