Complete MST You are given a complete graph † † ...

Complete MST
You are given a complete graph
†
†
on
N
N vertices with the edges having weights either
0
0 or
1
1.

Unfortunately you have forgotten which edges had weights of
1
1 and which had weights of
0
0. But you do remember that there were exactly
M
M edges with weight of
1
1.

Consider the Minimum Spanning Tree Problem on this complete graph. Let
W
W denote the sum of the weights of edges that are used in the minimum spanning tree.

Find the sum of all possible
W
W for complete graphs having exactly
M
M weight
1
1 edges.

†
†
A complete graph on
N
N vertices has
N
⋅
(
N
−
1
)
2
2
N⋅(N−1)
​
edge with an edge
(
X
,
Y
)
(X,Y) for all
1
≤
X
<
Y
≤
N
1≤X<Y≤N.

Input Format
The first line of input will contain a single integer
T
T, denoting the number of test cases.
The first and only line of each test case contains
N
N and
M
M - the number of nodes, and the number of weight
1
1 edges.
Output Format
For each test case, output on a new line the sum off all possible values of
W
W.

Constraints
1
≤
T
≤
1
0
4
1≤T≤10
4

2
≤
N
≤
1
0
9
2≤N≤10
9

0
≤
M
≤
N
⋅
(
N
−
1
)
2
0≤M≤
2
N⋅(N−1)
​

Sample 1:
Input
Output
8
3 2
3 3
4 3
6 12
6 9
15 80
15 30
2 0
1
2
1
5
3
28
3
0
Explanation:
Test case 1 : The only possible perimeter is
1

1. For example, one graph that obtains it is having edges
   (
   1
   ,
   2
   )
   (1,2) and
   (
   1
   ,
   3
   )
   (1,3) as weight
   1
   1, with the edge
   (
   2
   ,
   3
   )
   (2,3) being weight
   0

Then, one possible MST contains the edges
(
1
,
2
)
(1,2) and
(
2
,
3
)
(2,3), having a total weight of
1
1.

Test Case 2 : All edges are weight
1

1. So any MST will be of weight
   2

Test Case 3 : It is possible to obtain graphs with MST weight being
0
0 or
1
1.

Test Case 4 : It is possible to obtain graphs with MST weight being
2
2 or
3
3.

Did you like the problem statement?
More Info
Time limit1 secs
Memory limit1.5 GB
Source Limit50000 Bytes
import java.util.;
import java.lang.;
import java.io.*;

class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here

}

}

write a java solution