As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:

For an undirected graph  G  with  n  nodes and  m  edges, we can define the distance between  (i,j)  ( dist(i,j) ) as the length of the shortest path between  i  and  j . The length of a path is equal to the number of the edges on it. Specially, if there are no path between  i  and  j , we make  dist(i,j)  equal to  n .

Then, we can define the weight of the graph  G  ( wG ) as  ∑ni=1∑nj=1dist(i,j) .

Now, Yuta has  n  nodes, and he wants to choose no more than  m  pairs of nodes  (i,j)(i≠j)  and then link edges between each pair. In this way, he can get an undirected graph  G  with  n  nodes and no more than  m  edges.

Yuta wants to know the minimal value of  wG .

It is too difficult for Rikka. Can you help her?  

In the sample, Yuta can choose  (1,2),(1,4),(2,4),(2,3),(3,4) .

The first line contains a number  t(1≤t≤10) , the number of the testcases. 

For each testcase, the first line contains two numbers  n,m(1≤n≤106,1≤m≤1012) .

For each testcase, print a single line with a single number -- the answer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>

using namespace std;
typedef long long ll;
int main()
{
    int t;
    scanf("%d",&t);
    ll n,m;
    while(t--)
    {
        scanf("%lld%lld",&n,&m);
        ll tmp=n*(n-1)/2;
        ll result=0;
        if(m>=tmp)
        {
            result=n*(n-1);
        }
        else if(m>n-1&&m<tmp)
        {
            result=(n*(n-1))+(tmp-m)*2;
        }
        else
        {
            ll p=m+1,q=n-m-1;
            result=m*m*2+(n-m-1)*(n-m-2)*n+p*q*2*n;
        }
        cout<<result<<endl;
    }
    return 0;
}