启发式分治：给定$n$个数，求满足某种条件的点对数目或最大权值，而这个最大权值与点对$(a,b)$的区间$[a,b]$的区间最大/最小值有关。那么这时就可以考虑分治，对于区间$[L,R]$，找到最小/大值所在位置，然后处理横跨最小/大值所在位置的点对，然后递归处理子区间。

//#define LOCAL
#include <bits/stdc++.h>
using namespace std;
#define DBG printf("%d %s\n",__LINE__,__FUNCTION__)
#define ios ios::sync_with_stdio(false)
#define ctt cin.tie(0)
#define mem(t, v) memset ((t) , v, sizeof(t))
#define abs(x) ((x) >= 0 ? (x) : -(x))
#define LF putchar('\n')
#define SP putchar(' ')
#define eb emplace_back
#define mk make_pair
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define eps 1e-6
#define ri register int
#define LL long long
#define ULL unsigned long long

template<typename T> 
void read(T &x) {x = 0;char ch = getchar();LL f = 1;while(!isdigit(ch)){if(ch == '-')f *= -1;ch = getchar();}while(isdigit(ch)){x = x * 10 + ch - 48; ch = getchar();}x *= f;}
template<typename T, typename... Args> 
void read(T &first, Args& ... args) {read(first);read(args...);}
template<typename T>
void write(T arg) {T x = arg;if(x < 0) {putchar('-'); x =- x;}if(x > 9) {write(x / 10);}putchar(x % 10 + '0');}
template<typename T, typename ... Ts>
void write(T arg, Ts ... args) {write(arg);if(sizeof...(args) != 0) {putchar(' ');write(args ...);}}

const LL MOD = 1e9 + 7;
const int MAXN = 3e5 + 50;

int T, n, k, arr[MAXN], dp[MAXN][25], pos[MAXN][25], pr[MAXN], pl[MAXN], buk[MAXN];
LL ans;

void getst() {  //ST表预处理出任意区间最大值的下标
    for(ri i = 1; i <= n; ++i)
        dp[i][0] = arr[i], pos[i][0] = i;
    for(ri j = 1; (1 << j) <= n; ++j)
        for(ri i = 1; i + (1 << j) - 1 <= n; ++i)
            if(dp[i][j-1] >= dp[i+(1<<(j-1))][j-1])
                dp[i][j] = dp[i][j-1], pos[i][j] = pos[i][j-1];
            else
                dp[i][j] = dp[i+(1<<(j-1))][j-1], pos[i][j] = pos[i+(1<<(j-1))][j-1];
}

int rmq(int l, int r) {
    int k = log2(r - l + 1);
    return dp[l][k] >= dp[r-(1<<k)+1][k] ? pos[l][k] : pos[r-(1<<k)+1][k];
}

void prework() {  //找到第i个元素左/右端第一个开始重复的元素
    mem(buk, 0);
    buk[arr[1]] = 1;
    int r = 2;
    for(ri i = 1; i <= n; ++i) {
        while(r <= n && !buk[arr[r]])
            buk[arr[r]] = 1, ++r;
        buk[arr[i]] = 0;
        pr[i] = r - 1;
    }
    buk[arr[n]] = 1;
    r = n - 1;
    for(ri i = n; i >= 1; --i) {
        while(r >= 1 && !buk[arr[r]])
            buk[arr[r]] = 1, --r;
        buk[arr[i]] = 0;
        pl[i] = r + 1;
    }
}

void solve(int l, int r) {  //分治
    if(l > r)
        return ;
    int mid = rmq(l, r);
    if(r - mid > mid - l) {
        for(ri i = l; i <= mid; ++i) {
            int d = max(i + arr[mid] - k - 1, mid);
            int cr = min(pr[i], r);
            if(cr >= d)
                ans += cr - d + 1;
        }
    } else {
        for(ri i = r; i >= mid; --i) {
            int d = min(mid, i - arr[mid] + k + 1);
            int cl = max(pl[i], l);
            if(d >= cl)
                ans += d - cl + 1;
        }
    }
    solve(l, mid - 1);//下标为mid的值左右都已经计算过，所以递归时不包括mid
    solve(mid + 1, r);
}

int main() {
#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif
    read(T);
    while(T--) {
        read(n, k);
        for(ri i = 1; i <= n; ++i)
            read(arr[i]);
        getst();
        prework();
        ans = 0;
        solve(1, n);
        write(ans), LF;
    }
    return 0;
}