It's your birthday today! So, you ask your dad to buy a brand new bicycle. But your dad knows you are weak in math. Hence he gives you the following task. If you solve it, he will purchase the bicycle you want! The task is:
 
You are given a binary string. N denotes the length of a binary string and M denotes the number of occurrences of the character 1 in the string S.

Let F(S) be a function that gives the number of different substrings of string S, made up of the character 0 only. 
Let Sub_{l,r} denote the substring of S starting from l^{th} index and terminating at r^{th} index. Two substrings Sub_{p,q} and Sub_{r,s} are considered same if p = r and q = s otherwise the two substrings are considered different. 

Among all possible strings S of length N having exactly M occurrences of the character 1, print the minimum possible value of F(S).

------ Input Format ------ 

- First line of input contains a single integer T, denoting the number of test cases. Then the description of the T test case follows.
- Each test case contains one line of input.
- The first line contains two integers N and M.

------ Output Format ------ 

For each test case, output a single line answer containing an integer.

------ Constraints ------ 

$1 ≤ T ≤ 2 \cdot 10^{5}$
$1 ≤ N ≤ 10^{6}$
$0 ≤ M ≤ N$

----- Sample Input 1 ------ 
2
3 1
7 2
----- Sample Output 1 ------ 
2
7
----- explanation 1 ------ 
In the first test case, there exists only 3 binary strings of length $N$, having exactly $M$ occurrences of the character $1$.

For $S = 100$ value of $F(S) = 3$

For $S = 001$ value of $F(S) = 3$

For $S = 010$ value of $F(S) = 2$

So for string $S = 010$ we get a minimum value of $F(S) = 2$.

Difficulty: MEDIUM_HARD
Tags: Mathematics

Starter code:

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


def ti():
	return tuple(map(int, input().split()))

def li():
	return list(map(int, input().split()))

def si():
	return input().split()

def ii():
	return int(input())

def ip():
	return input()
for tastcas in range(int(input())):
	(n, m) = li()
	nn = n - 1
	zeros = n - m
	if zeros <= nn // 2 + 1:
		print(zeros)
	else:
		mM = m + 1
		t = zeros // mM
		inc = zeros - t * mM
		same = mM - inc
		print(same * (t * (t + 1)) // 2 + inc * ((t + 1) * (t + 2)) // 2)


def snek(n):
	s = n * (n + 1) // 2
	return s
t = int(input())
l = []
for i in range(t):
	(n, m) = list(map(int, input().split()))
	q = (n - m) // (m + 1)
	r = (n - m) % (m + 1)
	s = snek(q) * (m + 1 - r) + snek(q + 1) * r
	l.append(s)
for x in l:
	print(x)


def pro(n):
	sum = n * (n + 1) // 2
	return sum
try:
	t = int(input())
	val = 0
	l = []
	for i in range(t):
		(ns, ms) = list(input().split())
		(n, m) = (int(ns), int(ms))
		q = (n - m) // (m + 1)
		r = (n - m) % (m + 1)
		copy = q
		rc = r
		val = pro(q) * (m + 1 - r) + pro(q + 1) * r
		l.append(val)
	for i in l:
		print(i)
except:
	pass


import math
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	total_spaces = n - m
	regions = m + 1
	size = total_spaces // regions
	large = total_spaces % (m + 1)
	small = regions - large
	result = size * (size + 1) // 2 * small
	result += (size + 1) * (size + 2) // 2 * large
	print(result)


import math
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	d = a - b
	e = b + 1
	if b == 0:
		ans = a * (a + 1) // 2
	elif b >= a / 2:
		ans = d
	else:
		mx = math.ceil(d * 1.0 / e)
		mn = d // e
		if d < mx * e:
			diff = mx * e - d
			ans = diff * (mn * (mn + 1) // 2)
			ans += (e - diff) * (mx * (mx + 1) // 2)
		else:
			ans = e * (mx * (mx + 1) // 2)
	print(ans)


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


t = int(input())
for i in range(t):
	l = [int(n) for n in input().split()]
	sumi = 0
	noz = l[0] - l[1]
	spaces = l[1] + 1
	x = noz // spaces
	y = noz % spaces
	sumi = y * (x + 1) * (x + 2) // 2 + (spaces - y) * (x * (x + 1)) // 2
	print(sumi)


def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p ** 2, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = False
	prime[1] = False
import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
inp = lambda : int(input())
strng = lambda : input().strip()
jn = lambda x, l: x.join(map(str, l))
strl = lambda : list(input().strip())
mul = lambda : map(int, input().strip().split())
mulf = lambda : map(float, input().strip().split())
seq = lambda : list(map(int, input().strip().split()))
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))
mod = 1000000007

def p(x):
	return x * (x + 1) // 2
for _ in range(int(input())):
	(n, m) = mul()
	z = n - m
	m += 1
	x = ceil(z / m)
	y = x * m - z
	ans = y * p(z // m) + (m - y) * p(x)
	print(ans)


t = int(input())
for t in range(t):
	(n, m) = map(int, input().split())
	count_0 = n - m
	count_1 = m + 1
	if m >= n / 2:
		print(n - m)
	else:
		a = int(count_0 / count_1)
		b = int(count_0 % count_1)
		ans = (a + 1) * (a + 2) * b / 2
		ans += a * (a + 1) * (count_1 - b) / 2
		print(int(ans))


def func():
	zero = n - m
	p = zero // (m + 1)
	rem = zero % (m + 1)
	if rem == 0:
		print((m + 1) * p * (p + 1) // 2)
	else:
		print(rem * (p + 1) * (p + 2) // 2 + (m + 1 - rem) * (p * (p + 1) // 2))
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	func()


import sys
input = sys.stdin.readline

def func(n):
	return n * (n + 1) // 2
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	k = n - m
	if m == n:
		print(0)
		continue
	if m >= k:
		print(k)
		continue
	t = k // (m + 1)
	rem = k % (m + 1)
	ans = func(t) * (m + 1 - rem) + func(t + 1) * rem
	print(ans)


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


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


import heapq

def func(N, M):
	x = N - M
	if x <= M + 1:
		return x
	else:
		y = x // (M + 1)
		z = x % (M + 1)
		cnty = M + 1 - z
		cntz = y + 1
		return cnty * y * (y + 1) // 2 + z * (y + 1) * (y + 2) // 2
T = int(input())
for i in range(T):
	(N, M) = map(int, input().split())
	print(func(N, M))


def cost(num):
	return num * (num + 1) // 2
for i in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	zeroes = n - k
	parts = k + 1
	length = zeroes // parts
	rem = zeroes % parts
	res1 = parts - rem
	result = cost(length + 1) * rem + cost(length) * res1
	print(result)


def cst(n):
	return n * (n + 1) // 2
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	parts = m + 1
	zer = n - m
	l = zer // parts
	rem = zer - l * parts
	ans = rem * cst(l + 1) + (parts - rem) * cst(l)
	print(ans)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	numzeroes = n - m
	numparts = m + 1
	length = numzeroes // numparts
	rem = numzeroes - length * numparts
	x = length + 1
	ans = rem * (x * (x + 1) // 2) + (numparts - rem) * (length * (length + 1) // 2)
	print(ans)


def subst(value):
	return value * (value + 1) // 2
t = int(input())
while t != 0:
	(n, m) = map(int, input().split())
	numParts = m + 1
	numZeroes = n - m
	length = numZeroes // numParts
	remZeroes = numZeroes - numParts * length
	ans = remZeroes * subst(length + 1) + (numParts - remZeroes) * subst(length)
	print(ans)
	t -= 1


def func(n):
	return n * (n + 1) // 2
t = int(input())
for i in range(t):
	(n, m) = [int(i) for i in input().split()]
	zeros = n - m
	key = zeros // (m + 1)
	superkey = key + 1
	n_superkey = zeros - key * (m + 1)
	n_key = m + 1 - n_superkey
	sum_key = func(key)
	sum_superkey = func(superkey)
	ans = n_key * sum_key + n_superkey * sum_superkey
	print(ans)


for i in range(int(input())):
	s = 0
	(n, m) = map(int, input().split())
	d = n - m
	if d <= m + 1:
		print(d)
	else:
		e = d // (m + 1)
		f = d % (m + 1)
		c = m + 1 - f
		s = c * e * (e + 1) // 2 + f * (e + 1) * (e + 2) // 2
		print(s)


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


try:
	for i in range(int(input())):
		(n, m) = map(int, input().split())
		z = n - m
		if z % (m + 1) == 0:
			a = z // (m + 1)
			print((m + 1) * (a * (a + 1) // 2))
		else:
			b = z % (m + 1)
			a = z // (m + 1)
			print((m + 1 - b) * (a * (a + 1) // 2) + b * ((a + 1) * (a + 2)) // 2)
except EOFError:
	pass


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = n - m
	x = a // (m + 1)
	y = a - x * (m + 1)
	sum = y * (x + 1) * (x + 2) / 2 + (m + 1 - y) * x * (x + 1) / 2
	print(int(sum))


for i in range(int(input())):
	(n, m) = list(map(int, input().split()))
	n -= m
	a = 0
	while n > 0:
		a += n
		n -= m + 1
	print(a)


for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	zeroes = n - m
	parts = m + 1
	parts_len = zeroes // parts
	rem = zeroes - parts_len * parts

	def cost(x):
		return x * (x + 1) // 2
	print(rem * cost(parts_len + 1) + (parts - rem) * cost(parts_len))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	zc = n - m
	parts = m + 1
	length = zc // parts
	extra = zc - length * parts
	if m + 1 >= zc:
		print(zc)
	else:
		sumi = 0
		sumi += extra * (length + 1) * (length + 2) // 2
		sumi += (parts - extra) * length * (length + 1) // 2
		print(sumi)


def solve():
	(n, k) = list(map(int, input().split()))
	left = n - k
	k += 1
	value = left // k
	with_remainder = left % k
	value1 = ((value + 1) * (value + 1) + (value + 1)) / 2 * with_remainder
	value2 = (value * value + value) / 2 * (k - with_remainder)
	return int(value1 + value2)
for _ in range(int(input())):
	print(solve())


from math import ceil
tc = int(input())
for i in range(tc):
	(n, m) = map(int, input().split())
	if n == m:
		print(0)
		continue
	zeros = n - m
	pos_grps = m + 1
	if zeros <= pos_grps:
		print(zeros)
		continue
	grp_size = zeros // pos_grps
	rem = zeros % pos_grps
	ans = (grp_size + 1) * (grp_size + 2) // 2 * rem + grp_size * (grp_size + 1) // 2 * (pos_grps - rem)
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	if n == m:
		print(0)
	elif n - m <= m:
		print(n - m)
	else:
		z = n - m
		if z % (m + 1) == 0:
			x = z // (m + 1)
			s = (m + 1) * (x * (x + 1) // 2)
			print(s)
		else:
			r = z % (m + 1)
			x = z // (m + 1)
			s = (m + 1 - r) * (x * (x + 1) // 2) + r * ((x + 1) * (x + 2) // 2)
			print(s)


def cost(x):
	return x * (x + 1) // 2
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	numParts = m + 1
	numZeroes = n - m
	length = numZeroes // numParts
	remZeroes = numZeroes - length * numParts
	ans = remZeroes * cost(length + 1) + (numParts - remZeroes) * cost(length)
	print(ans)


import sys
import math

def sumation(n):
	return n * (n + 1) // 2
for t in range(int(input())):
	(n, k) = map(int, input().split())
	if n // 2 <= k:
		print(n - k)
	else:
		z = n - k
		rem = z % (k + 1)
		box = z // (k + 1)
		if rem == 0:
			ans = sumation(box) * (k + 1)
		else:
			totb = k + 1
			extra = rem
			og = totb - extra
			ans = sumation(box) * og
			ans += sumation(box + 1) * extra
		print(ans)


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


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


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


def min_f():
	(n, m) = map(int, input().split())
	x = n - m
	sum = 0
	if x <= m + 1:
		print(x)
	else:
		y = x // (m + 1)
		z = x % (m + 1)
		ty = m + 1 - z
		tx = y + 1
		s1 = ty * y * (y + 1) // 2
		s2 = z * (y + 1) * (y + 2) // 2
		print(s1 + s2)
for _ in range(int(input())):
	min_f()


from sys import stdin, stdout
inp_num = lambda : int(input())
inp_lis = lambda : list(map(int, input().split()))
for _ in range(inp_num()):
	(n, m) = map(int, input().split())
	if m >= n - m:
		print(n - m)
		continue
	else:
		d = (n - m) // (m + 1)
		re = (n - m) % (m + 1)
		print(int(d * (d + 1) / 2 * (m + 1) + re * (d + 1)))


def cost(l):
	return int(l * (l + 1) / 2)
for i in range(0, int(input())):
	(n, m) = map(int, input().split())
	ones = m
	z = n - m
	if m + 1 >= z:
		print(z)
	else:
		f = z // (m + 1)
		r = z % (m + 1)
		a = r * cost(f + 1) + (m + 1 - r) * cost(f)
		print(a)


T = int(input())
for i in range(T):
	(N, M) = map(int, input().split(' '))
	r = (N - M) // (M + 1)
	k = (-N - 1) % (M + 1)
	if k == 0:
		k = M + 1
	total = r * (r + 1) // 2 * k + (r + 1) * (r + 2) // 2 * (M + 1 - k)
	print(total)


def f(n, m):
	numparts = m + 1
	numzero = n - m
	length = numzero // numparts
	remzero = numzero - length * numparts
	cost = lambda x: x * (x + 1) // 2
	ans = remzero * cost(length + 1) + (numparts - remzero) * cost(length)
	return ans
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	print(f(n, m))


def func(n):
	return n * (n + 1) // 2
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	numparts = y + 1
	numzeroes = x - y
	l = numzeroes // numparts
	rem = numzeroes - l * numparts
	ans = rem * func(l + 1) + (numparts - rem) * func(l)
	print(ans)


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


def cost(x):
	return int(x * (x + 1) / 2)
T = int(input())
for _ in range(T):
	(n, m) = map(int, input().split())
	numParts = m + 1
	numZeros = n - m
	length = int(numZeros / numParts)
	remZeros = numZeros - length * numParts
	ans = remZeros * cost(length + 1) + (numParts - remZeros) * cost(length)
	print(ans)


def minzeroes(n, m):
	prts = m + 1
	res = 0
	zeroes = n - m
	il = zeroes // prts
	tmp = zeroes % prts
	res = (prts - tmp) * (il * (il + 1) // 2)
	res += tmp * ((il + 1) * (il + 2) // 2)
	return res
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	print(minzeroes(n, m))


a = int(input())

def cost(n):
	return n * (n + 1) // 2
for i in range(a):
	b = [int(j) for j in input().split()]
	totseg = b[1] + 1
	nzero = b[0] - b[1]
	seglen = nzero // totseg
	remzero = nzero - seglen * totseg
	fs = remzero * cost(seglen + 1) + (totseg - remzero) * cost(seglen)
	print(fs)


t = int(input())

def cost(i):
	return int(i * (i + 1) / 2)
for test in range(t):
	(n, m) = [int(x) for x in input().split()]
	g = m + 1
	c = (n - m) // g
	rz = n - m - g * c
	ans = rz * cost(c + 1) + (g - rz) * cost(c)
	print(ans)


def _func(a):
	k = a[0] - a[1]
	if k - 1 <= a[1]:
		return k
	else:
		z = k // (a[1] + 1)
		remz = k % (a[1] + 1)
		res = remz * (z + 1) * (z + 2) // 2 + (a[1] + 1 - remz) * z * (z + 1) // 2
		return res

def main():
	t = int(input())
	for _ in range(t):
		a = list(map(int, input().split()))
		print(_func(a))
main()


t = int(input())
while t:
	(n, m) = map(int, input().split())
	q = (n - m) // (m + 1)
	r = (n - m) % (m + 1)
	ans = r * ((q + 1) * (q + 2) // 2)
	ans += (m + 1 - r) * (q * (q + 1) // 2)
	print(ans)
	t -= 1


from math import floor

def main():
	for _ in range(int(input())):
		(n, m) = list(map(int, input().split()))
		r = n - m
		if r < m:
			print(r)
		else:
			exact = r / (m + 1)
			m_i_t = floor(exact)
			rem = r - m_i_t * (m + 1)
			x = m + 1 - rem
			print(x * (m_i_t * (m_i_t + 1) // 2) + rem * ((m_i_t + 1) * (m_i_t + 2) // 2))
main()


def solve():
	(x, y) = map(int, input().split())
	positions = y + 1
	zero = x - y
	ans = 0
	divide = zero // positions
	remaining = zero % positions
	number = remaining * ((divide + 1) * (divide + 2) // 2)
	ans = number + (positions - remaining) * ((divide + 1) * divide // 2)
	print(ans)
t = int(input())
while t != 0:
	solve()
	t -= 1


T = int(input())
for i in range(T):
	(n, m) = map(int, input().split())
	zero = n - m
	ans = 0
	if m == 0:
		print(n * (n + 1) // 2)
	elif m == n - 1:
		print('1')
	else:
		temp = int(zero // (m + 1))
		rem = zero % (m + 1)
		u = m + 1 - rem
		inc = temp + 1
		x = inc * (inc + 1) // 2
		x2 = temp * (temp + 1) // 2
		ans = x * rem + x2 * u
		print(ans)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	z = x - y
	k = z // (y + 1)
	suk = (k + 1) * k // 2
	sk = k + 1
	susk = (sk + 1) * sk // 2
	xsk = z - k * (y + 1)
	xk = y + 1 - xsk
	ans = xk * suk + xsk * susk
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = n - m
	if a <= m + 1:
		print(a)
	else:
		div = a // (m + 1)
		rem = a % (m + 1)
		countdiv = m + 1 - rem
		countrem = div + 1
		ans = countdiv * div * (div + 1) // 2 + rem * (div + 1) * (div + 2) // 2
		print(ans)


def sub(n, m):
	count = 0
	a = n - m
	if a <= m + 1:
		return a
	else:
		b = a // (m + 1)
		c = a % (m + 1)
		bb = m + 1 - c
		cc = b + 1
		count = bb * b * cc // 2 + c * cc * (cc + 1) // 2
		return count
for i in range(int(input())):
	(n, m) = list(map(int, input().split()))
	print(sub(n, m))


for i in range(int(input())):
	(a, b) = map(int, input().strip().split())
	c = a - b
	y = 0
	if c <= b + 1:
		print(c)
	else:
		y = c // (b + 1)
		z = c % (b + 1)
		cnt = b + 1 - z
		c2 = y + 1
		s = cnt * y * (y + 1) / 2 + z * (y + 1) * (y + 2) / 2
		print(int(s))


def solve():
	(n, m) = list(map(int, input().split()))
	a = n - m
	if a <= m + 1:
		print(a)
	else:
		b = a // (m + 1)
		z = a % (m + 1)
		cntb = m + 1 - z
		cnta = b + 1
		sum1 = cntb * b * (b + 1) // 2 + z * (b + 1) * (b + 2) // 2
		print(sum1)
for _ in range(int(input())):
	solve()


for i in range(int(input())):
	(n, m) = map(int, input().split())
	zeros = n - m
	grp = m + 1
	elmt = zeros // grp
	rem = zeros % grp
	ans = (elmt + 1) * (elmt + 2) / 2 * rem + elmt * (elmt + 1) / 2 * (grp - rem)
	print(int(ans))


import math
import os
import random
import re
import sys
T = int(input())
for _ in range(T):
	(N, M) = list(map(int, input().split()))
	z = N - M
	if z - 1 <= M:
		print(z)
	else:
		x = z // (M + 1)
		y = (M + 1) * x
		p = z - y
		sum = p * (x + 1) * (x + 2) // 2 + (M + 1 - p) * x * (x + 1) // 2
		print(sum)


import sys
for tc in range(int(input())):
	(n, m) = map(int, sys.stdin.readline().split())

	def findsubstring(n, m):
		bit = int(n - m)
		k = bit // (m + 1)
		sk = k + 1
		n_sk = bit - k * (m + 1)
		n_k = m + 1 - n_sk
		s_k = k * (k + 1) // 2
		s_sk = sk * (sk + 1) // 2
		partition1 = n_k * s_k
		partition2 = n_sk * s_sk
		res = abs(partition1 + partition2)
		return res
	print(findsubstring(n, m))


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


T = int(input())
for i in range(T):
	(N, M) = map(int, input().split())
	x = N - M
	if x <= M + 1:
		print(x)
	else:
		y = x // (M + 1)
		z = x % (M + 1)
		cnty = M + 1 - z
		cntx = y + 1
		sums = cnty * y * (y + 1) // 2 + z * (y + 1) * (y + 2) // 2
		print(sums)


for t in range(int(input())):
	(n, m) = map(int, input().split())
	cnt = 0
	a = n - m
	if a <= m + 1:
		print(a)
	else:
		y = a // (m + 1)
		z = a % (m + 1)
		countY = m + 1 - z
		countA = y + 1
		summ = countY * y * (y + 1) // 2 + z * (y + 1) * (y + 2) // 2
		print(summ)


def myfunc(z, n, o):
	if z > o + 1:
		t = z // (o + 1)
		l = z % (o + 1)
		l1 = o + 1 - l
		ans = l1 * (t * (t + 1)) // 2 + l * ((t + 1) * (t + 2)) // 2
		print(ans)
	else:
		print(z)
for _ in range(int(input())):
	(n, o) = map(int, input().split())
	z = n - o
	myfunc(z, n, o)


for i in range(int(input())):
	(x, y) = map(int, input().split())
	r = x - y
	if y >= r or y == r - 1:
		print(r)
	else:
		y += 1
		r1 = r // y
		r2 = r % y
		print(r2 * ((r1 + 1) * (r1 + 2) // 2) + (y - r2) * (r1 * (r1 + 1) // 2))


def solve(n, m):
	cnt = 0
	sum = 0
	(x, y, z) = (0, 0, 0)
	x = n - m
	if x <= m + 1:
		return x
	else:
		y = x // (m + 1)
		z = x % (m + 1)
		cnty = m + 1 - z
		cntx = y + 1
		sum1 = cnty * y * (y + 1) // 2 + z * (y + 1) * (y + 2) // 2
		return sum1
t = int(input())
while t > 0:
	(n, m) = map(int, input().split())
	print(solve(n, m))
	t -= 1


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	n -= k
	nn = n // (k + 1)
	mod = n % (k + 1)
	cnt = (k + 1 - mod) * (nn * (nn + 1)) // 2
	cnt_ = 0
	cnt += mod * ((nn + 1) * (nn + 2)) // 2
	print(cnt)