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