//
// Created by 16373 on 2024/12/15.
//
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=1e6+10;
typedef long long ll;
int a[N];
int pre[N],suf[N];
struct node{
    int l,r,mx;
}tree[4*N];
void pushup(int p){
    tree[p].mx=max(tree[p<<1].mx,tree[p<<1|1].mx);
}
void build(int p,int l,int r){
    tree[p]={l,r,a[l]};
    if(l==r){
        return;
    }
    int m=l+r>>1;
    build(p<<1,l,m);
    build(p<<1|1,m+1,r);
    pushup(p);
}

int query(int p,int l,int r){
    if(l<=tree[p].l && tree[p].r<=r){
        return tree[p].mx;
    }
    int m=tree[p].l+tree[p].r>>1;
    int mx=0;
    if(l<=m) mx=max(query(p<<1,l,r),mx);
    if(m<r) mx=max(query(p<<1|1,l,r),mx);
    return mx;
}
set<int> v[N];
void solve(){
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) v[i].clear();
    build(1,1,n);
    int mx=0,pos=0;
    for(int i=1;i<=n;i++){
        if(a[i]>=mx){
            mx=a[i];
            pos=i;
        }
        pre[i]=pos;
    }
    mx=0,pos=n+1;
    for(int i=n;i>=1;i--){
        if(a[i]>=mx){
            mx=a[i];
            pos=i;
        }
        suf[i]=pos;
    }
    ll res=0;
    for(int i=1;i<=n;i++){
        v[a[i]].insert(i);
        if(v[a[i]].size()==k){
            int ft=*v[a[i]].begin();
            if(query(1,ft,i)==a[i]){
                int ls,rs;
                if(pre[ft]==ft) ls=0;
                else ls=pre[ft];
                if(suf[i]==i) rs=n+1;
                else rs=suf[i];
                res+=(ll)(ft-ls)+(rs-i);
            }
            v[a[i]].erase(v[a[i]].begin());
        }
    }
    cout<<res<<'\n';
}
signed main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}