#include <bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f
#define ll long long
#define pii pair<int, int>
#define tii tuple<int, int, int>
#define db double
#define all(a) a.begin(), a.end()
using namespace std;
const int maxn = 1e6 + 10;
const int mod = 998244353;
int L[maxn], R[maxn];
int arr[maxn], nxt[maxn];
vector<int> pos[maxn];
void solve() {
    stack<int> stk;
    int n, k; cin >> n >> k;
    for (int i = 1; i <= n; i++) pos[i].clear(), nxt[i] = 0;
    for (int i = 1; i <= n; i++) cin >> arr[i];
    for (int i = 1; i <= n; i++) {
        while (!stk.empty() && arr[i] >= arr[stk.top()])
            stk.pop();
        if (!stk.empty()) L[i] = stk.top();
        stk.push(i);
        pos[arr[i]].push_back(i);
    }
    while (!stk.empty()) stk.pop();
    for (int i = n; i; i--) {
        while (!stk.empty() && arr[i] >= arr[stk.top()]) stk.pop();
        if (!stk.empty()) R[i] = stk.top();
        else R[i] = n + 1;
        stk.push(i);
    }
    for (int i = 1; i <= n; i++) {
        pos[i].push_back(n + 1);
        if (pos[i].size() > k) {
            for (int j = 0; j + k < pos[i].size(); j++)
                nxt[pos[i][j]] = pos[i][j + k];
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int l = i - L[i], r = min(nxt[i], R[i]) - 1 - i;
        if (l > 0 && r > 0) ans += l * r;
    }
    cout << ans << "\n";
}
signed main() {
    // freopen("1.in", "r", stdin);
    // freopen("1.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}