C. Функция Айоуба
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Айоуб думает, что он очень умный человек, поэтому он придумал функцию $$$f(s)$$$, где $$$s$$$ это бинарная строка (строка, содержащая только символы «0» и «1»). Функция $$$f(s)$$$ равна количеству подстрок строки $$$s$$$, которые содержат хотя бы один символ, равный «1».

Более формально, $$$f(s)$$$ равно количеству пар целых чисел $$$(l, r)$$$, таких что $$$1 \leq l \leq r \leq |s|$$$ (где $$$|s|$$$ равно длине строки $$$s$$$), таких что хотя бы один из символов $$$s_l, s_{l+1}, \ldots, s_r$$$ равен «1».

Например, если $$$s = $$$«01010», то $$$f(s) = 12$$$, потому что есть $$$12$$$ таких пар $$$(l, r)$$$: $$$(1, 2), (1, 3), (1, 4), (1, 5), (2, 2), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 4), (4, 5)$$$.

Айоуб также думает, что он умнее Махмуда, поэтому дал ему два целых числа $$$n$$$ и $$$m$$$ и следующую задачу. По всем бинарным строкам $$$s$$$ длины $$$n$$$, которые содержат ровно $$$m$$$ символов, равных «1», найдите максимальное значение $$$f(s)$$$.

У Махмуда не получилось решить эту задачу, поэтому он попросил вас о помощи. Можете ли вы помочь ему?

Входные данные

Входные данные состоят из нескольких тестовых случаев. Первая строка содержит единственное целое число $$$t$$$ ($$$1 \leq t \leq 10^5$$$)  — количество тестовых случаев. Далее следует описание тестовых случаев в следующем формате.

Единственная строка для каждого тестового случая содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq n \leq 10^{9}$$$, $$$0 \leq m \leq n$$$) — длина строки и количество символов, равных «1» в ней.

Выходные данные

Для каждого тестового случая выведите единственное целое число — максимальное значение $$$f(s)$$$ по всем строкам $$$s$$$ длины $$$n$$$, которые содержат ровно $$$m$$$ символов, равных «1».

Пример
Входные данные
5
3 1
3 2
3 3
4 0
5 2
Выходные данные
4
5
6
0
12
Примечание

В первом тестовом случае, существует только $$$3$$$ строки длины $$$3$$$, которые содержат ровно $$$1$$$ символ, равный «1». Эти строки это: $$$s_1 = $$$«100», $$$s_2 = $$$«010», $$$s_3 = $$$«001». Значения $$$f$$$ для них это: $$$f(s_1) = 3, f(s_2) = 4, f(s_3) = 3$$$, поэтому максимальное значение это $$$4$$$ и ответ равен $$$4$$$.

Во втором тестовом случае, строка $$$s$$$ для которой максимальное значение функции это «101».

Во третьем тестовом случае, строка $$$s$$$ для которой максимальное значение функции это «111».

В четвертом тестовом случае, единственная строка $$$s$$$ длины $$$4$$$, которая содержит ровно $$$0$$$ символов, равных «1» это «0000» и значение функции $$$f$$$ для этой строки это $$$0$$$, поэтому ответ равен $$$0$$$.

В пятом тестовом случае, строка $$$s$$$ с максимальным значением функции это «01010» и она была подробно разобрана в качестве примера в тексте условия задачи.