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