Problem Description

一开始有 n个数，他们按 1…n的顺序排列，要求交换最多 m对数字（同一个数字可以参与多次交换），使得逆序对数目最大。

对于一个序列 A，如果存在正整数 i, j使得1≤i<j≤n 而且 A[i] > A[j]，则 <A[i],A[j]> 这个有序对称为 A的一个逆序对。

Input

第一行一个正整数test (1≤test≤100000) 表示数据组数。

对于每组数据，一行两个整数 n，m (1≤n≤1000000,0≤m≤1000000) 表示数字个数和最多可以交换的数字对数。

Output

对于每组数据，一行一个整数表示答案。

Sample Input

1
2
3
4
5
6
7
6
1 1
2 0
2 1
3 1
4 1
4 2

Sample Output

1
2
3
4
5
6
0
0
1
3
5
6
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#include<vector>
#include<algorithm>

using namespace std;

// 对每个（n, 1）结果都为：2 * n - 3
int com(int n)
{
    int com = 2 * n - 3;
    return com;
}

// 把（n, m）转换为（n, 1）, (n -2, 1)...(n - 2m + 2, 1)之和的形式并利用com()计算结果
int arr(int n, int m)
{
    int res = 0;
    for (int i = 0; i < m; i++)
    {
        res += com(n - 2 * i);
        //cout << i <<" "<< res<<endl;
    }
    return res;
}

vector<int> compute() 
{
    
    int groupNum;
    cin >> groupNum;
    vector<int> output;
    for (int i = 0; i < groupNum; i++)
    {
        int n;
        int m;
        //cout << "choiseNum:" << choiseNum << endl;
        cin >> n;
            //cout << "b:" << b << endl;
        cin >> m;
            //cout << "c:" << c << endl;
        if (n == 1 || m == 0)
        {
            output.push_back(0);
        }
        else {
            if (2 * m < n)
            {
                int res = arr(n, m);
                output.push_back(res);
            }
            else 
            {
                m = n / 2;
                int res = arr(n, m);
                output.push_back(res);
            }
        }
        }
    return output;
    }

int main()
{
    vector<int> res = compute();
    for (int i = 0; i < res.size(); i++)
    {
        //cout << res[i];
        printf("%d\n", res[i]);
    }
    return 0;
}