#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
struct node
{
    ll key;
    ll l,r;
}num[500001];
ll a[500001];
ll pos[500001];
ll pre[81],nex[81];

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,k;
        scanf("%d %d",&n,&k);
        num[1].l=-1;
        num[n].r=-1;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            if(i!=1) num[i].l=i-1;
            if(i!=n) num[i].r=i+1;
            num[i].key=a[i];
            pos[a[i]]=i;
        }
        ll sum=0;
        for(int i=1;i<=n;i++)
        {
            fill(pre+1,pre+k+1,-1);
            fill(nex+1,nex+k+1,-1);
            ll po=pos[i];
            ll temp=num[po].l;
            int ret=1;
            pre[0]=nex[0]=po;
            while(temp!=-1 && ret<=k)
            {
                pre[ret++]=temp;
                temp=num[temp].l;
            }
            temp=num[po].r;
            ret=1;
            while(temp!=-1 && ret<=k)
            {
                nex[ret++]=temp;
                temp=num[temp].r;
            }
            /*
            for(int i=1;i<=k;i++) cout<<pre[i]<<‘ ‘;
            cout<<endl;
            for(int i=1;i<=k;i++) cout<<nex[i]<<‘ ‘;
            cout<<endl;
            */
            for(int j=0;j<k;j++)
            {
                if(pre[k-j-1]==-1 || nex[j]==-1) continue;
                ll ans=pre[k-j-1]-pre[k-j];
                ll ans2=nex[j+1]-nex[j];
                if(pre[k-j]==-1) ans=pre[k-j-1];
                if(nex[j+1]==-1) ans2=n-nex[j]+1;
              //  cout<<ans<<‘ ‘<<ans2<<endl;
                sum+=ans*ans2*(ll)i;
            }
            // delete
            ll nl=num[po].l;
            ll nr=num[po].r;
            num[nl].r=nr;
            num[nr].l=nl;
        }
        printf("%lld\n",sum);
    }
    return 0;
}