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