#include <iostream>
#include <vector>

using namespace std;

typedef  long long LL;
 
const int N = 1e6+10 ;
const int inf =  1e8+10 ; 

int n ,  k  ;
int a[N], q[N] , l[N] , r[N] , pos[N] ;  

void solve( ) {
	cin >> n >> k ; 
	vector< vector<int> > num( n + 1 ,vector<int>( 1 , 0 ) ) ; 
	for(int i = 1 ;i <=n ; ++ i ) cin >>a[i] , pos[i] = num[a[i]].size() , num[a[i]].push_back( i )  ;
	int tt = 0  ;
	a[0] = a[n + 1] = inf ;q[++tt] = 0 ;
	for(int i = 1; i <=n ; ++ i ) {
		while( a[ q[tt]] <= a[i] ) --tt ;
		l[i] = q[tt] ; 
		q[++tt] = i ; 
	}
	tt= 0 ; q[++tt] = n + 1 ;
	LL ans = 0  ;
	for(int i = n ; i ; -- i ) {
		while( a[q[tt]] <= a[i] ) --tt ;
		r[i] = q[tt] ; 
		q[ ++tt]  = i ; 
		if( pos[i] + k -1 < num[a[i]].size()  ) 
			ans += 1ll * (  i - max( num[a[i]][ pos[i] -1 ]  , l[i]) ) *max( 0 , r[i]  - num[a[i]][pos[i] + k -1 ] ) ; 
	}
	cout << ans <<"\n";
} 	

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
//	freopen("in.in" , "r" , stdin) ;
	int T ; cin >>T ;
	while(T-- ){	
		solve() ;  
   	}        
 	return  0 ;
}