#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define endl '\n'
using PII=pair<int,int>;

const int N=1e6+5;

int a[N],l[N],r[N],idx[N];
vector<int>id[N];
void solve(){
    int n,k;
    cin>>n>>k;
    ll ans=0;
    vector<int>stk;
    for(int i=1;i<=n;i++)id[i].clear();
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        idx[i]=id[a[i]].size();
        id[a[i]].push_back(i);
        while(stk.size()&&a[stk.back()]<a[i])
            stk.pop_back();
        if(stk.size())
            l[i] = stk.back();
        else
            l[i] = 0;
        
        stk.push_back(i);
        l[i]++;
    }
    stk.clear();
    for (int i = n; i >= 1;i--){
        while(stk.size()&&a[stk.back()]<=a[i])
            stk.pop_back();
        if(stk.size())
            r[i] = stk.back();
        else
            r[i] = n + 1;
        stk.push_back(i);
        r[i]--;
    }
    for (int i = 1; i <= n;i++){
        if(idx[i]+k<=id[a[i]].size()){
            int tmp=id[a[i]][idx[i]+k-1];
            if(idx[i]+k+1<=id[a[i]].size()){
                r[i]=min(r[i],id[a[i]][idx[i]+k]-1);
            }
            ans+=1ll*(i-l[i]+1)*(r[i]-tmp+1);
            // cout << l[i] << ' ' << r[i] <<' '<<tmp<< endl;
        }
        
    }
    cout<<ans<<endl;
}

signed main(){
    // freopen("data.in","r",stdin);
    ios::sync_with_stdio(0),cin.tie(0);
    int t;
    cin>>t;
    while(t--)solve();
}