CF1301C.Ayoub's function

Ayoub thinks that he is a very smart person, so he created a function $f(s)$ , where $s$ is a binary string (a string which contains only symbols "0" and "1"). The function $f(s)$ is equal to the number of substrings in the string $s$ that contains at least one symbol, that is equal to "1".

More formally, $f(s)$ is equal to the number of pairs of integers $(l, r)$ , such that $1 \leq l \leq r \leq |s|$ (where $|s|$ is equal to the length of string $s$ ), such that at least one of the symbols $s_l, s_{l+1}, \ldots, s_r$ is equal to "1".

For example, if $s = $ "01010" then $f(s) = 12$ , because there are $12$ such pairs $(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)$ .

Ayoub also thinks that he is smarter than Mahmoud so he gave him two integers $n$ and $m$ and asked him this problem. For all binary strings $s$ of length $n$ which contains exactly $m$ symbols equal to "1", find the maximum value of $f(s)$ .

Mahmoud couldn't solve the problem so he asked you for help. Can you help him?

The input consists of multiple test cases. The first line contains a single integer $t$ ( $1 \leq t \leq 10^5$ ) — the number of test cases. The description of the test cases follows.

The only line for each test case contains two integers $n$ , $m$ ( $1 \leq n \leq 10^{9}$ , $0 \leq m \leq n$ ) — the length of the string and the number of symbols equal to "1" in it.

For every test case print one integer number — the maximum value of $f(s)$ over all strings $s$ of length $n$ , which has exactly $m$ symbols, equal to "1".

In the first test case, there exists only $3$ strings of length $3$ , which has exactly $1$ symbol, equal to "1". These strings are: $s_1 = $ "100", $s_2 = $ "010", $s_3 = $ "001". The values of $f$ for them are: $f(s_1) = 3, f(s_2) = 4, f(s_3) = 3$ , so the maximum value is $4$ and the answer is $4$ .

In the second test case, the string $s$ with the maximum value is "101".

In the third test case, the string $s$ with the maximum value is "111".

In the fourth test case, the only string $s$ of length $4$ , which has exactly $0$ symbols, equal to "1" is "0000" and the value of $f$ for that string is $0$ , so the answer is $0$ .

In the fifth test case, the string $s$ with the maximum value is "01010" and it is described as an example in the problem statement.