#include <bits/stdc++.h>

using namespace std;
#define pii pair<int, int>
#define Genshin_Impact return
#define start 0
const int mod = 998244353;
const int N = 1e6 + 10;
int a[N];
map<pii, int> pos;
int num[N], cnt[N];
struct node
{
    int l, r, maxn;
} tr[N << 2];
void pushup(int u)
{
    tr[u].maxn = max(tr[u << 1].maxn, tr[u << 1 | 1].maxn);
}

void build(int u, int l, int r)
{
    tr[u] = {l, r, 0};
    if (l == r)
    {
        tr[u].maxn = a[l];
        return;
    }
    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u);
    return;
}

int query(int u, int l, int r, int x, int op)
{
    if (tr[u].l == tr[u].r)
    {
        if (tr[u].maxn > x)
            return tr[u].l;
        return -1;
    }
    int mid = tr[u].l + tr[u].r >> 1;
    if (r <= mid)
        return query(u << 1, l, r, x, op);
    else if (l >= mid + 1)
        return query(u << 1 | 1, l, r, x, op);
    else
    {
        if (op)
        {
            int pos = query(u << 1 | 1, l, r, x, op);
            if (pos != -1)
                return pos;
            return query(u << 1, l, r, x, op);
        }
        else
        {
            int pos = query(u << 1, l, r, x, op);
            if (pos != -1)
                return pos;
            return query(u << 1 | 1, l, r, x, op);
        }
    }
}
void solve()
{
    pos.clear();
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        num[i] = 0, cnt[i] = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        cnt[a[i]]++;
        num[i] = cnt[a[i]];
        pos[{a[i], cnt[a[i]]}] = i;
    }
    build(1, 1, n);
    long long ans = 0;
    for (int i = 1; i <= n; i++)
    {
        int x = a[i], posrr, ns;
        if (cnt[x] >= num[i] + k - 1)
        {
            int posrl = pos[{x, num[i] + k - 1}];
            if (query(1, i, posrl, x, 1) != -1)
                continue;
            if (cnt[x] >= num[i] + k)
                posrr = pos[{x, num[i] + k}];
            else
                posrr = n + 1;
            int q = query(1, posrl, n, x, 0);
            if (q != -1)
                posrr = min(posrr, q);
            int numr = posrr - posrl;
            // cout << i << ": " << x << ' ' << posrl << ' ' << posrr << ' ';
            int l = max(0, query(1, 1, i, x, 1));
            // cout << l << '\n';
            ans += 1ll * (i - l) * numr;
        }
    }
    cout << ans << '\n';
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(20);
    int t = 1;
    cin >> t;
    while (t--)
        solve();
    Genshin_Impact start;
}