Kanade's sum

Problem Description

Give you an array $A[1..n]$of length $n$. Let $f(l,r,k)$ be the k-th largest element of $A[l..r]$. Specially , $f(l,r,k)=0$ if $r-l+1<k$. Give you $k$ , you need to calculate $\sum_{l=1}^{n}\sum_{r=l}^{n}f(l,r,k)$ There are T test cases. $1\leq T\leq 10$ $k\leq min(n,80)$ $A[1..n] ~is~a~permutation~of~[1..n]$ $\sum n\leq 5*10^5$

Input

There is only one integer T on first line. For each test case,there are only two integers $n$,$k$ on first line,and the second line consists of $n$ integers which means the array $A[1..n]$

Output

For each test case,output an integer, which means the answer.

Sample Input

1



5 2



1 2 3 4 5

Sample Output

30

Source

2017 Multi-University Training Contest - Team 3

https://acm.hdu.edu.cn/showproblem.php?pid=6058