import sys
input = sys.stdin.readline
T = int(input())
NM = [list(map(int, input().split())) for _ in range(T)]
for n, m in NM:
    m2 = m*2
    ans = (n%m2)*((n+1)%m2)%m2
    print(ans//2)