#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i = a; i <= b; ++i)
#define ROF(i,a,b) for(int i = a; i >= b; --i)
typedef long long ll;
using namespace std;
inline int rd() {
    int r = 0; bool w = false; char ch = getchar();
    while( ch < '0' || ch > '9' ) w = !(ch^45), ch = getchar();
    while( ch >= '0' && ch <= '9' ) r = (r<<1) + (r<<3) + (ch^48), ch = getchar();
    return w ? -r : r;
}

#define MAXN 300000
int n, k;
int a[MAXN+5];
int lbig[MAXN+5], rbig[MAXN+5];
int lind[MAXN+5], rind[MAXN+5];
int st[MAXN+5];
int vis[MAXN+5];
ll ans;
void dcon(int l , int r) {
    if( l == r ) {
        ans += a[l] <= (1 + k);
        return;
    }
    // printf("solving: %d %d\n", l, r);
    int mid = (l + r) >> 1;
    int tl = mid+1, tr = r, trbig = r, tlbig = mid+1;
    int nowmax = 0;
    ROF(i, mid, l) {
        if( nowmax < a[i] ) trbig = rbig[i] - 1, nowmax = a[i];
        tr = min(tr, rind[i]-1);
        if( tr < mid+1 ) break;
        tl = max(max(tl - 1, mid+1), a[i] - k + i - 1);
        ans += max(min(tr, trbig) - tl + 1, 0);
        // printf("leftpoint: %d, l: %d, r:%d\n", i, tl, min(tr, trbig));
    }
    tl = l, tr = mid;
    nowmax = 0;
    FOR(i,mid+1,r) {
        if( nowmax < a[i] ) tlbig = lbig[i] + 1, nowmax = a[i];
        tl = max(tl, lind[i]+1);
        if( tl > mid ) break;
        tr = min(min(tr + 1, mid), i + 1 - a[i] + k);
        ans += max(tr - max(tlbig, tl) + 1, 0);
        // printf("rightpoint: %d, l: %d, r:%d\n", i, max(tlbig, tl), tr);
    }
    dcon(l, mid);
    dcon(mid+1, r);
}
void solve() {
    n = rd(), k = rd();
    FOR(i,1,n) a[i] = rd();
    st[0] = 0;
    FOR(i,1,n) {
        while( st[0] && a[st[st[0]]] < a[i] ) --st[0];
        lbig[i] = st[0] ? st[st[0]] : 0;
        st[++st[0]] = i;
    }
    st[0] = 0;
    ROF(i,n,1) {
        while( st[0] && a[st[st[0]]] < a[i] ) --st[0];
        rbig[i] = st[0] ? st[st[0]] : n+1;
        st[++st[0]] = i;
    }
    FOR(i,1,n) vis[i] = 0;
    FOR(i,1,n) {
        lind[i] = vis[a[i]];
        vis[a[i]] = i;
    }
    FOR(i,1,n) vis[i] = n+1;
    ROF(i,n,1) {
        rind[i] = vis[a[i]];
        vis[a[i]] = i;
    }
    ans = 0;
    dcon(1, n);
    printf("%lld\n", ans);
}

int main() {
    int T = rd(); while( T-- ) solve();
    return 0;
}