The chef is fond of triangles. He has a task for you. You are given n point out of which only k are collinear. Find the number of triangles that can be formed from these n points.
You have to perform the above task for a number of test cases.

Input
The first line of input contains the number of test cases, t.
Then t lines follow each containing 2 space separated integers n and k.

Output
The output contains t lines each containing the answer for that particular test case. Each line contains the number triangles that can be formed for that particular test.

Constraints
1<=t<=1000
3<=n<=1000000
3<=k<=n

Example
Input:
1
30 5
Output:
4050

见题面

见题面