Little Kevin had never heard the word 'Infinitum'. So he asked his mentor to explain the word to him. His mentor knew that 'Infinitum' is a very large number. To show him how big Infinitum can be, his mentor gave him a challenge: to sum the numbers from 1 up to N. The sum started to get really large and was out of long long int range. And so the lesson was clear.

Now his mentor introduced him to the concept of mod and asked him to retain only the remainder instead of the big number. And then, he gave him a formula to compute:

$\sum_{i=1}^{N}\left(i\%m\right)$

Input Format 

The first line contains T, the number of test cases. 

T lines follow, each containing 2 space separated integers N m

Output Format 

Print the result on new line corresponding to each test case.  

Constraint 

1 ≤ T ≤ 1000 

1 ≤ N ≤ 10^{9} 

1 ≤ m ≤ 10^{9}

Sample Input  

3
10 5
10 3
5 5

Sample Output  

20
10
10

Explanation 

Case 1: N = 10 m = 5, 

1%5 + 2%5 + 3%5 + 4%5 + 5%5 + 6%5 + 7%5 + 8%5 + 9%5 + 10%5 = 20. 

Similar explanation follows for Case 2 and 3.

Difficulty: MEDIUM_HARD
Tags: Matrices

Starter code:

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


T = int(input())
for _ in range(T):
	(N, m) = [int(_) for _ in input().split()]
	(d, r) = divmod(N, m)
	print((m - 1) * m // 2 * d + r * (r + 1) // 2)


T = int(input())
for _ in range(T):
	[n, m] = list(map(int, input().split()))
	(r, q) = (n % m, n // m)
	answer = m * (m - 1) // 2 * q + r * (r + 1) // 2
	print(answer)


T = int(input())
for t in range(T):
	(N, m) = map(int, input().split())
	q = N // m
	r = N % m
	ans = q * (m * (m - 1) // 2) + r * (r + 1) // 2
	print(ans)


T = int(input())
for ca in range(T):
	(N, m) = (int(i) for i in input().split())
	a = N // m
	N %= m
	print((m - 1) * m // 2 * a + N * (N + 1) // 2)


def sum_to_n(n):
	if n % 2 == 0:
		return int(n / 2) * (n + 1)
	return int((n + 1) / 2) * n
count = int(input())
for i in range(count):
	(n, m) = map(int, input().split(' '))
	total = 0
	if n >= m:
		unit = sum_to_n(m - 1)
		total += unit * int(n / m)
		n = n % m
	total += sum_to_n(n)
	print(total)


def groupsum(val):
	return val * (val + 1) // 2
max = int(input())
for i in range(0, max):
	templist = list(map(int, input().split()))
	counts = templist[0] // templist[1]
	rem = templist[0] - counts * templist[1]
	gsum = groupsum(templist[1] - 1)
	total = gsum * counts + groupsum(rem)
	print(total)


import sys
nums = list(map(int, sys.stdin.read().split()))
for i in range(nums[0]):
	N = nums[i * 2 + 1]
	m = nums[i * 2 + 2]
	a = (N + 1) // m
	b = (N + 1) % m
	ans = m * (m - 1) // 2 * a + b * (b - 1) // 2
	print(ans)


t = int(input())
for i in range(t):
	s = input().strip().split()
	n = int(s[0])
	m = int(s[1])
	a = n // m
	b = n % m
	sum1 = m * (m - 1) // 2
	sum2 = b * (b + 1) // 2
	ans = a * sum1 + sum2
	print(ans)


test = int(input())
for _ in range(test):
	stri = input().split()
	(n, m) = (int(stri[0]), int(stri[1]))
	numbers = 0
	numbers = (m - 1) * m // 2
	multi = n // m
	answer = numbers * multi
	multi = n % m
	answer += multi * (multi + 1) // 2
	print(answer)


def ar_sum(x):
	if x % 2 == 0:
		return x // 2 * (x + 1)
	else:
		return x * ((x + 1) // 2)
t = int(input())
for tt in range(t):
	data = input().rstrip().split()
	n = int(data[0])
	m = int(data[1])
	mod = n % m
	ans = n // m * ar_sum(m - 1) + ar_sum(mod)
	print(ans)


t = int(input())
for i in range(t):
	sum = 0
	(n, m) = map(int, input().split())
	sum1 = m * (m - 1) // 2
	div = n // m
	rem = n % m
	sum2 = rem * (rem + 1) // 2
	sum = div * sum1 + sum2
	print(sum)


import sys
triangular_number = lambda n: n * (n + 1) // 2
T = int(sys.stdin.readline())
for _ in range(T):
	(N, m) = list(map(int, sys.stdin.readline().split()))
	print(N // m * triangular_number(m - 1) + triangular_number(N % m))


from sys import stdin
T = int(stdin.readline())

def tri(n):
	return n * (n + 1) // 2
for _ in range(T):
	(N, m) = [int(s) for s in stdin.readline().split()]
	print(N // m * tri(m - 1) + tri(N % m))


n = int(input())

def ss(x):
	return x * (x + 1) // 2
for _ in range(n):
	(a, b) = map(int, input().split())
	s = ss(min(a, b - 1))
	if b <= a:
		n = a // b
		if n > 0:
			s = s * n
		s += ss(a % b)
	print(s)


def mod_sum(m):
	if m % 2 == 0:
		return (m - 2) // 2 * m + m // 2
	else:
		return (m - 1) // 2 * m

def solve(n, m):
	(div, mod) = divmod(n, m)
	sum = div * mod_sum(m) + mod_sum(mod + 1)
	return sum
t = int(input())
for i in range(t):
	(n, m) = [int(l) for l in input().split(' ')]
	print(solve(n, m))


import sys
inp = sys.stdin.read()
inp = inp.split(sep='\n')
T = inp.pop(0)

def Summ(N):
	return (1 + N) * N // 2
for i in range(int(T)):
	nm = inp[i].split()
	N = int(nm[0])
	m = int(nm[1])
	print(int(N // m * Summ(m - 1)) + int(Summ(N % m)))


T = int(input())
for test_case in range(T):
	(N, m) = (int(x) for x in input().split())
	mod_sum = m * (m - 1) // 2
	multiplier = N // m
	mod = N % m
	print(mod_sum * multiplier + mod * (mod + 1) // 2)


t = int(input())
for i in range(t):
	sum = 0
	(N, m) = map(int, input().split())
	t = N // m
	sum1 = (m - 1) * m // 2
	s = N % m
	sum2 = s * (s + 1) // 2
	sum = t * sum1 + sum2
	print(int(sum))


from sys import stdin as cin, stdout as cout
from math import log
for t in range(int(cin.readline())):
	(n, m) = map(int, cin.readline().split())
	r = int(n / m)
	k = n % m
	a = (m - 1) * m // 2
	b = k * (k + 1) // 2
	s = r * a + b
	print(s)


for _ in range(int(input())):
	temp = input()
	(x, y) = temp.split()
	n = int(x)
	m = int(y)
	s = 0
	if (n >= 1 and n <= 1000000000) and (m >= 1 and m <= 1000000000):
		t = n // m
		s = (m - 1) * m // 2
		s = s * t
		r = n % m
		s += r * (r + 1) // 2
		print(int(s))


def sumTo(n):
	return n * (n + 1) // 2
for i in range(int(input())):
	(n, m) = map(int, input().split())
	s = n // m * sumTo(m - 1) + sumTo(n - n // m * m)
	print(s)


def checkt(z):
	if 1 <= z <= 1000:
		return True

def checkn(z):
	if 1 <= z <= 10 ** 9:
		return True

def checkm(z):
	if 1 <= z <= 10 ** 9:
		return True

def gsum(n, m):
	return n // m * msum(m - 1) + msum(n - n // m * m)

def msum(x):
	return x * (x + 1) // 2
t = int(input())
if checkt(t):
	for i in range(t):
		ip = input().split(' ')
		n = int(ip[0])
		m = int(ip[1])
		if checkn(n) and checkm(m):
			print(gsum(n, m))


cases = int(input())
for i in range(cases):
	(n, m) = [int(i) for i in input().split(' ')]
	s = m * (m - 1) // 2
	q = int(n // m)
	r = n % m
	r = r * (r + 1) // 2
	print(s * q + r)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	if m > n:
		print(n * (n + 1) // 2)
	else:
		sm = m * (m - 1) // 2
		print(sm * (n // m) + n % m * (n % m + 1) // 2)


def sumTo(n):
	return n * (n + 1) // 2
T = int(input())
for i in range(T):
	(N, m) = map(int, input().split())
	(q, r) = divmod(N, m)
	result = q * sumTo(m - 1) + sumTo(r)
	print(result)


def solve(n, m):
	return n // m * m * (m - 1) // 2 + n % m * (n % m + 1) // 2
for t in range(int(input())):
	print(solve(*[int(x) for x in input().split(' ')]))


def ModSum(n, m):
	r = n % m
	k = (n - r) // m
	s1 = k * m * (m - 1) // 2
	s2 = r * (r + 1) // 2
	return s1 + s2
T = int(input())
while T:
	T = T - 1
	(N, M) = [int(i) for i in input().split()]
	print(ModSum(N, M))


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


for t in range(int(input())):
	(n, m) = [int(i) for i in input().split()]
	n_mod_m = n % m
	count = n // m
	ans = (n_mod_m + 1) * n_mod_m // 2
	ans += m * (m - 1) * count // 2
	print(ans)


t = int(input())
while t != 0:
	t = t - 1
	line = input()
	(n, m) = line.split()
	n = int(n)
	m = int(m)
	sum = 0
	if n % m == 0:
		summ = 0
		summ = int(m * (m - 1) // 2)
		sum = summ * int(n / m)
		print(sum)
	else:
		summ = 0
		summ = int(m * (m - 1) // 2)
		sum = summ * int(n / m)
		rem = n % m
		mul = rem * (rem + 1)
		remsum = mul // 2
		sum = sum + remsum
		print(sum)


for i in range(int(input())):
	(N, m) = tuple(map(int, input().split()))
	a = N // m
	sum = a * (m * (m - 1)) // 2
	N -= a * m
	i = 1
	sum += N * (N + 1) // 2
	print(sum)


for i in range(int(input())):
	(n, m) = [int(j) for j in input().split(' ')]
	print(n // m * (m * (m - 1)) // 2 + n % m * (n % m + 1) // 2)


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


def arithmetic_sum(n):
	return n * (n + 1) // 2
cases = int(input())
for case in range(cases):
	params = list(map(int, str(input()).strip().split(' ')))
	N = params[0]
	m = params[1]
	if N < m:
		print(arithmetic_sum(N))
	else:
		total_cycles = N // m
		remainder_number_of_terms = N % m
		cycle_sum = arithmetic_sum(m - 1)
		remainder_sum = arithmetic_sum(remainder_number_of_terms)
		print(total_cycles * cycle_sum + remainder_sum)


def sumn(n):
	return n * (n + 1) // 2
T = int(input())
for _ in range(T):
	(N, m) = [int(i) for i in input().split()]
	l = N // m
	n = m - 1
	r = N % m
	print(l * sumn(n) + sumn(r))


def easysum(x1, x, y):
	count = 0
	for i in range(x1, x + 1):
		count = count + i % y
	return count
test = int(input())
while test != 0:
	list = [int(i) for i in input().strip().split()]
	x = list[0]
	y = list[1]
	z = x % y
	vv = y * (y - 1) // 2
	div = x // y
	if z == 0:
		zz = vv * div
		print(zz)
	elif z != 0:
		vvv = vv * div
		val = z * (z + 1) // 2
		print(val + vvv)
	test = test - 1


def solve(N, m):
	(d, r) = divmod(N, m)
	return d * m * (m - 1) // 2 + r * (r + 1) // 2
T = int(input())
for _ in range(T):
	(N, m) = (int(_) for _ in input().split())
	print(solve(N, m))


import sys
T = int(sys.stdin.readline())
triangular_number = lambda n: n * (n + 1) // 2
for _ in range(T):
	(N, m) = list(map(int, sys.stdin.readline().split()))
	print(N // m * triangular_number(m - 1) + triangular_number(N % m))


T = int(input())
triangle_num = lambda n: n * (n + 1) // 2
for i in range(T):
	(N, m) = [int(x) for x in input().rstrip().split()]
	print(N // m * triangle_num(m - 1) + triangle_num(N % m))


T = int(input())
for t in range(T):
	splitted = input().split()
	(N, m) = (int(splitted[0]), int(splitted[1]))
	intPart = N // m
	sum = intPart * ((m - 1) * m)
	N1 = N % m
	if N1 != 0:
		sum += (1 + N1) * N1
	print(int(sum // 2))


numTests = int(input())
for test in range(numTests):
	(N, m) = [int(num) for num in input().split(' ')]
	print(m * (m - 1) // 2 * (N // m) + N % m * (N % m + 1) // 2)


T = int(input())
for t in range(T):
	tmp = input().split()
	n = int(tmp[0])
	m = int(tmp[1])
	tmp = 0
	mult = 0
	ans = 0
	if m > n:
		if n % 2 == 0:
			ans = (1 + n) * (n // 2)
		else:
			ans = n * ((n - 1) // 2) + n
	else:
		tmp = n % m
		mult = (n - tmp) // m
		if (m - 1) % 2 == 0:
			ans = m * ((m - 1) // 2) * mult
		else:
			ans = ((m - 1) * ((m - 2) // 2) + m - 1) * mult
		if tmp % 2 == 0:
			ans += (tmp + 1) * (tmp // 2)
		else:
			ans += tmp * ((tmp - 1) // 2) + tmp
	print(int(ans))


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	bsum = m * (m - 1) // 2
	r = n % m
	print(n // m * bsum + r * (r + 1) // 2)


x = int(input())
for i in range(x):
	(n, m) = input().split(' ')
	n = int(n)
	m = int(m)
	print(int(m * (m - 1) // 2) * int(n // m) + int(n % m * (n % m + 1) // 2))


t = int(input())
while t > 0:
	t -= 1
	(n, m) = (int(i) for i in input().split(' '))
	div = n // m
	rem = n % m
	sum_m = m * (m - 1) // 2
	print(sum_m * div + rem * (rem + 1) // 2)


import sys
T = int(sys.stdin.readline())
triangular_number = lambda n: n * (n + 1) // 2
for _ in range(T):
	(N, m) = list(map(int, sys.stdin.readline().split()))
	print(N // m * triangular_number(m - 1) + triangular_number(N % m))


def sumModSeries(N, m):
	wrapping_sum = m * (m - 1) // 2
	left = N % m
	return wrapping_sum * (N // m) + left * (left + 1) // 2
t = int(input())
for case in range(t):
	tokens = input().split()
	N = int(tokens[0])
	m = int(tokens[1])
	print(sumModSeries(N, m))


import sys
T = int(sys.stdin.readline())
triangular_number = lambda n: n * (n + 1) // 2
for _ in range(T):
	(N, m) = list(map(int, sys.stdin.readline().split()))
	print(N // m * triangular_number(m - 1) + triangular_number(N % m))


import sys
T = int(sys.stdin.readline())
triangular_number = lambda n: n * (n + 1) // 2
for _ in range(T):
	(N, m) = list(map(int, sys.stdin.readline().split()))
	print(N // m * triangular_number(m - 1) + triangular_number(N % m))


import sys
t = int(input())
while t:
	(n, m) = list(map(int, sys.stdin.readline().split()))
	Sum = int(n // m * (m * (m - 1)) // 2 + n % m * (n % m + 1) // 2)
	print(Sum)
	t -= 1


t = int(input())
for _ in range(t):
	[n, m] = list(map(int, input().strip().split()))
	p = n % m
	q = n // m
	ans = q * (m * (m - 1)) // 2 + (p + 1) * (p + 2) // 2 - (p + 1)
	print(ans)


t = int(input())
for i in range(t):
	(n, m) = [int(j) for j in input().split()]
	cycle_sum = m * (m - 1) // 2
	total = cycle_sum * (n // m)
	rem = n % m
	total += rem * (rem + 1) // 2
	print(total)


def get(t, mod):
	v = mod * (mod - 1) >> 1
	v = v * (t // mod)
	t = t % mod
	v = v + (t * (t + 1) >> 1)
	print(v)

def solve():
	n = int(input())
	for i in range(0, n):
		(t, mod) = map(int, input().split())
		get(t, mod)
solve()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	if m > n:
		print(n * (n + 1) // 2)
	else:
		partial_sum = m * (m - 1) // 2
		rem = n % m
		print(partial_sum * (n // m) + rem * (rem + 1) // 2)


for t in range(int(input())):
	(N, m) = map(int, input().split())
	q = N // m
	r = N % m
	print(q * m * (m - 1) // 2 + r * (r + 1) // 2)


T = int(input())
for T_cnt in range(T):
	[N, m] = [int(x) for x in input().split()]
	outp = N // m * m * (m - 1) >> 1
	rem = N % m
	outp += rem * (rem + 1) >> 1
	print(outp)


def summod(N, m):
	s = 0
	for i in range(1, N + 1):
		s = s + i % m
	return s
cases = int(input())
for case in range(cases):
	(N, m) = [int(x) for x in input().split()]
	d = N // m
	diff = N - d * m
	sumtom = (m - 1) * m // 2
	total = d * sumtom + diff * (diff + 1) // 2
	print(total)


import sys
T = int(sys.stdin.readline())
triangular_number = lambda n: n * (n + 1) // 2
for _ in range(T):
	(N, m) = list(map(int, sys.stdin.readline().split()))
	print(N // m * triangular_number(m - 1) + triangular_number(N % m))


t = int(input())
for i in range(t):
	a = input().split()
	n = int(a[0])
	m = int(a[1])
	s = n // m * ((m - 1) * m // 2) + n % m * (n % m + 1) // 2
	print(s)


for t in range(int(input())):
	(N, m) = map(int, input().strip().split(' '))
	m_remainders = N % m
	total = (m - 1) * m // 2 * (N // m) + (m_remainders + 1) * m_remainders // 2
	print(total)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	(q, r) = divmod(n, m)
	print(q * m * (m - 1) // 2 + r * (r + 1) // 2)


T = int(input())
for _ in range(T):
	(N, m) = [int(x) for x in input().split()]
	s = m * (m - 1) // 2
	n = N // m
	mod = N % m
	print(s * n + mod * (mod + 1) // 2)


for t in range(int(input())):
	(n, m) = map(int, input().split())
	cnt = n // m
	rem = n % m
	tot = cnt * (m * (m - 1)) // 2 + rem * (rem + 1) // 2
	print(tot)


for _ in range(int(input().strip())):
	(N, m) = map(int, input().strip().split(' '))
	sumM = m * (m - 1) // 2
	divM = N // m
	modM = N % m
	print(divM * sumM + modM * (modM + 1) // 2)


def do(N, m):
	(q, r) = divmod(N, m)
	return (q * m * (m - 1) + r * (r + 1)) // 2
for _ in range(int(input().strip())):
	(N, m) = (int(i) for i in input().strip().split())
	print(do(N, m))


def my(n, m):
	r = n % m
	if n >= m:
		return m * (m - 1) // 2 * (n // m) + r * (r + 1) // 2
	else:
		return n * (n + 1) // 2

def this(n, m):
	s = 0
	for i in range(1, n + 1):
		s += i % m
	return s
t = int(input())
for i in range(t):
	(n, m) = [int(i) for i in input().split()]
	if i < t - 1:
		print(my(n, m))
	else:
		print(my(n, m), end='')


t = int(input())
inputs = [input() for i in range(t)]
for i in range(t):
	currentInput = inputs[i]
	n = int(currentInput.split()[0])
	m = int(currentInput.split()[1])
	sumToM = (m - 1) * m // 2
	times = n // m
	remain = n % m
	sumation = sumToM * times + remain * (remain + 1) // 2
	print(sumation)


from decimal import *
getcontext().prec = 20
for __ in range(int(input())):
	(N, m) = [int(x) for x in input().split()]
	a = int(N / m)
	b = N % m
	A = Decimal(a * m * (m - 1))
	B = Decimal(b * (b + 1))
	print(Decimal((A + B) / 2))


n = int(input())
for _ in range(n):
	line = list(map(int, input().split()))
	(a, b) = line
	bSum = b * (b - 1) // 2
	totalSum = a // b * bSum
	asd = divmod(a, b)[1]
	totalSum += asd * (asd + 1) // 2
	print(totalSum)


T = int(input())
for _ in range(T):
	(N, m) = [int(t) for t in input().split()]
	full_sum_value = m * (m - 1) // 2
	full_sum_count = N // m
	p = N % m
	half_sum_value = p * (p + 1) // 2
	result = full_sum_value * full_sum_count + half_sum_value
	print(result)


t = int(input())
for i in range(t):
	(n, m) = [int(x) for x in input().split(' ')]
	count = (m - 1) * m // 2 * (n // m)
	extra = n - n // m * m
	count += extra * (extra + 1) // 2
	print(count)


for _ in range(int(input())):
	(N, m) = map(int, input().split())
	q = N // m
	r = N % m
	print(int(q * m * (m - 1) // 2 + r * (r + 1) // 2))


def delim_list():
	return [int(x) for x in input().split(' ')]
t = int(input())
for it in range(t):
	total = 0
	(n, m) = delim_list()
	m_sum = m * (m - 1) // 2
	k = n // m
	total += m_sum * k
	n -= m * k
	total += n * (n + 1) // 2
	print(total)


T = int(input())
my_list = [tuple(map(int, input().split(' '))) for _ in range(T)]
for item in my_list:
	N = item[0]
	M = item[1]
	k = N % M
	print(N // M * M * (M - 1) // 2 + k * (k + 1) // 2)


import sys

def solve(n, m):
	cycles = n // m
	r = n % m
	print('n=%d m=%d cycles=%d r=%d' % (n, m, cycles, r), file=sys.stderr)
	sm = (m - 1) * m // 2 * cycles
	sm += r * (r + 1) // 2
	return sm
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	print(solve(n, m))


for i in range(int(input())):
	(N, m) = map(int, input().split())
	k = N % m
	print(m * (m - 1) // 2 * (N // m) + k * (k + 1) // 2)


def s(n):
	if n == 0:
		return 0
	return n * (n + 1) // 2
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	d = n // m
	r = n % m
	print(d * s(m - 1) + s(r))


t = int(input())
for _ in range(t):
	nm = list(map(int, input().split()))
	n = nm[0]
	m = nm[1]
	quot = n // m
	rem = n % m
	ans = quot * ((m ** 2 - m) // 2) + (rem ** 2 + rem) // 2
	print(ans)


T = int(input().strip())
for t in range(0, T):
	(N, m) = map(int, input().strip().split(' '))
	rem = N % m
	print(N // m * (m * (m - 1) // 2) + rem * (rem + 1) // 2)


print('\n'.join(map(lambda n, m: str((n // m * (m - 1) * m + (n % m + 1) * (n % m)) // 2), *zip(*(map(int, input().split()) for _ in range(int(input())))))))


t = int(input())
while t > 0:
	(n, m) = [int(x) for x in input().split()]
	lastRound = n % m * (n % m + 1) // 2
	ans = m * (m - 1) // 2 * (n // m) + lastRound
	print(ans)
	t -= 1


for i in range(int(input())):
	(N, m) = input().strip().split(' ')
	(N, m) = [int(N), int(m)]
	suma = m * (m - 1) // 2
	q = N // m
	r = N % m
	print(suma * q + r * (r + 1) // 2)


t = int(input().strip())
for _ in range(t):
	(n, m) = map(int, input().strip().split(' '))
	r = n % m
	k = n // m
	result = k * m * (m - 1) // 2 + r * (r + 1) // 2
	print(result)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	times = n // m
	extra = n % m * (n % m + 1) // 2
	print(m * (m - 1) // 2 * times + extra)


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


T = int(input())
for t in range(T):
	(N, m) = input().split()
	(N, m) = [int(N), int(m)]
	(p, q) = divmod(N, m)
	print(p * m * (m - 1) // 2 + q * (q + 1) // 2)


T = int(input())
for _ in range(T):
	(N, m) = [int(i) for i in input().split()]
	remainder_sum = lambda N, m: (m - 1) * m // 2 * (N // m) + N % m * (N % m + 1) // 2
	print(remainder_sum(N, m))


T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	till_M = M * M - M >> 1
	(Quo, Rem) = divmod(N, M)
	sumRem = Rem * Rem + Rem >> 1
	print(Quo * till_M + sumRem)


for i in range(int(input())):
	(n, m) = list(map(int, input().split()))
	smallSum = m * (m - 1) // 2
	mainPart = n // m * smallSum
	extra = n % m * (n % m + 1) // 2
	print(mainPart + extra)


import sys
t = int(input().strip())
for i in range(t):
	(n, m) = [int(valore) for valore in input().strip().split(' ')]
	quoziente = n // m
	resto = n % m
	print(m * (m - 1) // 2 * quoziente + (resto + 1) * resto // 2)


t = int(input())
for _ in range(t):
	(N, m) = map(int, input().split())
	(quotient, remainder) = (N // m, N % m)
	s = lambda x: x * (x + 1) // 2
	total = quotient * s(m - 1)
	total += s(remainder)
	print(total)


T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	if M <= N and M > 0:
		q = N % M
		r = N // M * (M * (M - 1) // 2)
		r += q * (q + 1) // 2
		print(r)
	else:
		print(N * (N + 1) // 2)


t = int(input().strip())
for i in range(t):
	Nm = input().strip().split(' ')
	(N, m) = (int(Nm[0]), int(Nm[1]))
	sum_unit = m * (m - 1) // 2
	remain = N % m * (N % m + 1) // 2
	print(sum_unit * (N // m) + remain)


for T in range(int(input())):
	(N, m) = map(int, input().split())
	R = N % m
	Q = int(N / m)
	s1 = R * (R + 1) // 2
	s1 += Q * (m * (m - 1)) // 2
	print('{}'.format(s1))


def calcula_soma(n, m):
	r = n % m
	return (n - r) * (m - 1) // 2 + (1 + r) * r // 2
for i in range(0, int(input())):
	(n, m) = input().split()
	print(int(calcula_soma(int(n), int(m))))


T = int(input().strip())
for dummyT in range(T):
	(N, m) = [int(x) for x in input().strip().split()]
	k = N % m
	S = N // m * (m * (m - 1)) // 2 + k * (k + 1) // 2
	print(S)


ans = []
for i in range(int(input())):
	(N, m) = list(map(int, input().split()))
	k = N % m
	s = (m - 1) * m // 2 * (N // m) + k * (k + 1) // 2
	ans.append(s)
for i in ans:
	print(i)