T = int(input())

for _ in range(T):
    N, M = map(int, input().split())
    s = N%M
    t = (N+1)%M
    print(((s*t)//2)%M)