#pragma GCC optimizeA("Ofast")
#pragma GCC optimizeA("inline")
#pragma GCC optimizeA("unroll-loops")

#include <bits/stdc++.h>
#define int LL
#define DEBUG_VAR(x) { cerr << "* "#x" = " << x << endl; }
#define DEBUG_ARR(arr, l, r) { \
    cerr << "* "#arr"[" << l << ", " << r << "]: "; \
    for(int it = l; it <= r; it++) { \
        cerr << arr[it] << " "; \
    } \
    cerr << endl; \
}
using namespace std;
using LL = long long;

const int N = 3e5 + 5;

#define memset_n(arr, byte, n) { memset((arr), (byte), (n)*(sizeof(*arr))); }

int n, m;
int a[N];
int stk[N], top, shh;

int delta_q23;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q12, q23;

int ins[N]; // max i where in stk 
int st[N]; // state of max i: 1, 2, 3 

int cnt[N];
int most_previous = 1;

int get_l(int r)
{
    if(ins[r] == shh) {
        return most_previous;
    } else {
        // DEBUG_VAR(ins[r]);
        return stk[ins[r] - 1] + 1;
    } 
}

int get_used_len(int r, int i)
{
    int l = get_l(r);
    return min(r - l + 1, m + i + 1 - a[r] - l + 1);
}

void solve()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    memset_n(ins, -1, n + 1);
    memset_n(st, -1, n + 1);
    memset_n(cnt, 0, n + 1);
    memset_n(stk, 0, n + 1);
    while(q12.size()) q12.pop();
    while(q23.size()) q23.pop();

    LL cnt2 = 0; 
    LL sum = 0;
    LL ans = 0;
    delta_q23 = 0;

    top = 0; shh = 1;
    
    most_previous = 1;
    for(int i = 1; i <= n; i++) {
        // DEBUG_VAR("=============================");
        while(top >= shh && a[stk[top]] <= a[i]) {
            int r = stk[top];   // DEBUG_VAR(r); DEBUG_VAR(ins[r]);
            int l = get_l(r);
            // DEBUG_VAR(st[r]);
            if(st[r] == 1) {
                // pass 
            } else if(st[r] == 2) {
                cnt2--;
                sum -= get_used_len(r, i - 1); 
                // DEBUG_VAR(get_used_len(r, i - 1));
                // DEBUG_VAR(get_l(r));
                // DEBUG_VAR(shh);
            } else {
                sum -= (r - l + 1);
            }
            st[r] = -1;
            ins[r] = -1;
            top--;
        }
        // DEBUG_VAR(sum);
        stk[++top] = i;
        ins[i] = top;
        int r = i;
        int l = get_l(r);
        int len = (r - l + 1);
        
        // DEBUG_ARR(stk, shh, top);
        // DEBUG_VAR(len);
        // DEBUG_VAR(r); DEBUG_VAR(l);
        if(a[r] + r <= m + (i - 1) + 1) {
            st[r] = 3;
            sum += len;
        } else if(a[r] + l > m + (i - 1) + 1) {
            st[r] = 1;
            q12.emplace(a[r] + l, r);
        } else {
            st[r] = 2;
            cnt2++;
            int used_len = get_used_len(r, i - 1);
            sum += used_len;
            q23.emplace(len - used_len - delta_q23, r);
        }

        // DEBUG_VAR(sum);

        // move most_previous
        int new_most_previous = most_previous;
        while(cnt[a[i]]) {
            cnt[a[new_most_previous]]--;
            new_most_previous++;
        }
        cnt[a[i]]++;

        l = most_previous;
        while(shh <= top) {
            int r = stk[shh];

            // DEBUG_VAR(r);
            // DEBUG_VAR(new_most_previous);
            // DEBUG_VAR(st[r]);
            if(l >= new_most_previous) {
                break;
            } else if(r < new_most_previous) { // delete all;
                if(st[r] == 1) {
                    // pass 
                } else if(st[r] == 2) {
                    int used_len = m + (i - 1) + 1 - a[r] - l + 1;
                    cnt2--;
                    sum -= used_len;
                } else {
                    assert(st[r] == 3);
                    sum -= r - l + 1;
                }
                ins[r] = -1;
                st[r] = -1;
                shh++;
            } else {
                // DEBUG_VAR(st[r]);
                if(st[r] == 1) {
                    // pass
                } else if(st[r] == 2) {
                    // DEBUG_VAR("HERE");
                    int new_l = new_most_previous;
                    int used_len = m + (i - 1) + 1 - a[r] - l + 1;
                    int used_l = l + used_len - 1;

                    if(new_l > used_l) {
                        st[r] = 1;
                        q12.emplace(a[r] + l, r);
                        cnt2--;
                    } 
                    sum -= new_l - l;
                } else if(st[r] == 3) {
                    // DEBUG_VAR(r);
                    int new_l = new_most_previous;
                    sum -= new_l - l;
                    // DEBUG_VAR(new_l);
                    // DEBUG_VAR(l);
                }
                break;
            }
            l = r + 1;
        }
        most_previous = new_most_previous;

        // DEBUG_VAR(sum);
        // i-1 -> i
        delta_q23--;
        while(q12.size()) {
            auto [val, r] = q12.top();
            if(ins[r] == -1 || st[r] != 1) {
                q12.pop();
                continue;
            } else if(val <= m + i + 1) {
                q12.pop();
                cnt2++;
                int l = get_l(r);
                int len = (r - l + 1);
                q23.emplace(len - 1 - delta_q23, r);
                st[r] = 2;
            } else {
                break;
            }
        }

        while(q23.size()) {
            auto [val, r] = q23.top();
            if(ins[r] == -1 || st[r] != 2) {
                q23.pop();
                continue;
            } else if(val + delta_q23 < 0) {
                q23.pop();
                cnt2--;
                st[r] = 3;
            } else {
                break;
            }
        }

        sum += cnt2;
        ans += sum;
        // DEBUG_VAR(sum);
        // DEBUG_VAR(top);
    }

    cout << ans << endl;
}

signed main()
{
    // freopen("1.in", "r", stdin);
    ios::sync_with_stdio(false); cin.tie(nullptr);

    int T; cin >> T;
    while(T--) {
        solve();
    }

    return 0;
}