#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        vector<int> a(n);
        map<int, int> f;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            f[a[i]]++;
        }
        int c = 0;
        while (true) {
            int l = f.begin()->first;
            int r = f.rbegin()->first;
            if (r <= l + 1 + k) 
                break;
            int fl = f[l];
            int fr = f[r];
            int b = min(fl, fr);
            c += b * k;

            f[l] -= b;
            if (f[l] == 0) 
                f.erase(l);
            f[l + 1] += b;

            f[r] -= b;
            if (f[r] == 0) 
                f.erase(r);
            f[r - 1] += b;
        }
        int s = 0;
        for (auto &p : f) {
            int v = p.first;
            int x = p.second;
            s += x * (v * (v + 1) / 2);
        }
        cout << c + s << "\n";
    }
    return 0;
}