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