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