Ayoub认为自己是一个非常聪明的人,所以他创建了一个函数$$$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)$$$。
Ayoub也认为他比Mahmoud聪明,所以给了他两个整数$$$n$$$和$$$m$$$并问他这个问题。对于长度为 $$$n$$$ 且恰好包含等于“1”的 $$$m$$$ 符号的所有二进制字符串 $$$s$$$,找到 $$$f(s)$$$ 的最大值。
Mahmoud 无法解决问题,因此他向您寻求帮助。你能帮助他吗?
输入
输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的唯一行包含两个整数 $$$n$$$, $$$m$$$ ($$$1 \leq n \leq 10^{9}$$$, $$$0 \leq m \leq n$$$) - 字符串的长度和其中等于“1”的符号数量。
输出
对于每个测试用例,打印一个整数 - $$$f(s)$$$ 在长度为 $$$n$$$ 的所有字符串 $$$s$$$ 上的最大值,该字符串恰好具有 $$$m$$$ 符号,等于“1”。
示例
输入 #1
5 3 1 3 2 3 3 4 0 5 2
输出 #1
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”。
在第四个测试用例中,唯一长度为 $$$4$$$ 的字符串 $$$s$$$ 恰好具有 $$$0$$$ 符号,等于“1”,是“0000”,并且该字符串的 $$$f$$$ 值为 $$$0$$$,因此答案为 $$$0$$$。
在第五个测试用例中,最大值的字符串 $$$s$$$ 为“01010”,并在问题陈述中作为示例进行了描述。