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

More formally, f(s)f(s) is equal to the number of pairs of integers (l,r)(l,r), such that 1≤l≤r≤|s|1≤l≤r≤|s| (where |s||s| is equal to the length of string ss), such that at least one of the symbols sl,sl+1,…,srsl,sl+1,…,sr is equal to “1”.

For example, if s=s=“01010” then f(s)=12f(s)=12, because there are 1212 such pairs (l,r)(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)(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 nn and mm and asked him this problem. For all binary strings ss of length nn which contains exactly mm symbols equal to “1”, find the maximum value of f(s)f(s).

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

Input
The input consists of multiple test cases. The first line contains a single integer tt (1≤t≤1051≤t≤105) — the number of test cases. The description of the test cases follows.

The only line for each test case contains two integers nn, mm (1≤n≤1091≤n≤109, 0≤m≤n0≤m≤n) — the length of the string and the number of symbols equal to “1” in it.

Output
For every test case print one integer number — the maximum value of f(s)f(s) over all strings ss of length nn, which has exactly mm symbols, equal to “1”.

Example

Input
5
3 1
3 2
3 3
4 0
5 2
Output
4
5
6
0
12
Note
In the first test case, there exists only 33 strings of length 33, which has exactly 11 symbol, equal to “1”. These strings are: s1=s1=“100”, s2=s2=“010”, s3=s3=“001”. The values of ff for them are: f(s1)=3,f(s2)=4,f(s3)=3f(s1)=3,f(s2)=4,f(s3)=3, so the maximum value is 44 and the answer is 44.

In the second test case, the string ss with the maximum value is “101”.

In the third test case, the string ss with the maximum value is “111”.

In the fourth test case, the only string ss of length 44, which has exactly 00 symbols, equal to “1” is “0000” and the value of ff for that string is 00, so the answer is 00.

In the fifth test case, the string ss with the maximum value is “01010” and it is described as an example in the problem statement.
這種思維題真的不能用等級來評定，會的人覺得它跟A一樣的水平，不會的就是和F一樣的水平。
思路：我們求含有1的字符串最大個數(shù)，那么就是求含有0的字符串最小個數(shù)。因為求1不是很好求。一共有(n+1)*n/2個子字符串，一共有m個1，所以一共有n-m個0。對這n-m個0，一共有m+1個位置可以放置。因為要求最小，所以每個位置的0的個數(shù)應(yīng)當(dāng)取平均值cnt1=(n-m)/(m+1)。但是呢，不一定整除，有可能會有cnt2=(n-m)%(m+1)個位置是cnt1+1個0的，所以我們最后再減去(cnt1+1) * (cnt2).最后答案等于(n+1)*n/2-(cnt1+1) * cnt1/2 *（m+1）-(cnt1+1) * (cnt2).
代碼如下：

#include<bits/stdc++.h> #define ll long long using namespace std;ll n,m;int main() {int t;scanf("%d",&t);while(t--){cin>>n>>m;ll ans1=(n+1ll)*n/2ll;//總共的子字符串?dāng)?shù)ll cnt1=(n-m)/(m+1ll);ll cnt2=(n-m)%(m+1ll);cout<<ans1-(cnt1*(cnt1+1ll)/2ll)*(m+1ll)-(cnt1+1ll)*cnt2<<endl;}return 0; }

努力加油a啊，(^o)/~

總結(jié)

以上是生活随笔為你收集整理的Ayoub's function CodeForces - 1301C（组合数学）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。