Ayoub's function

题意翻译

- 规定函数 $f(s)$ 等于使得从字符串 $s$ 的第 $l$ 个字符到第 $r$ 个字符中至少一个符号等于 `1` 的整数对 $(l,r)$ 的数目（$1\le l\le r\le |s|$，其中 $|s|$ 等于字符串 $s$ 的长度），且字符串 $s$ 是一个二进制字符串（仅包含字符 `0` 和 `1`）。 - 例如，若 $s=$ `01010`，则 $f(s)=12$，因为满足条件的 $(l,r)$ 有 $12$ 对：$(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$。 - 现要求对于长度为 $n$，且**正好**包含 $m$ 个字符 `1` 的所有二进制字符串 $s$，找到 $f(s)$ 的最大值。

题目描述

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".

输入输出样例

输入样例 #1

5
3 1
3 2
3 3
4 0
5 2

输出样例 #1

4
5
6
0
12

说明

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.