As a lonely explorer, you are full of curiosity about the mysterious power of arrays. On your journey through the past, you heard a legend about arrays: every array hides a mysterious power. If the frequency of the maximum value in an array is at least a certain threshold $k$, this array has a "power value" of $1$; otherwise, it has no power value. The "power level" of an array is the sum of the power values of all its subarrays.

Given an array of length $n$, you are eager to know the power level of this array.

Recall: A subarray is a contiguous segment of elements in an array. For example, for the array $a = [3, 2, 1, 3, 2]$, $[2, 1], [1, 3], [3, 2, 1]$ are subarrays, but $[3, 3], [1, 4]$ are not.

Input

The first line contains the number of test cases $T$ ($1 \le T \le 10^6$).

For each test case: The first line contains two integers $n$ and $k$ ($1 \le k \le n \le 10^6$), representing the length of the array and the threshold. The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), representing the given array.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

Output

For each test case, output a single integer on a new line, representing the power level of the array.

Examples

Input 1

2
5 2
1 3 3 2 2
4 3
1 4 2 1

Output 1

7
0

Note

In the first example, the subarrays $[1, 3, 3], [1, 3, 3, 2], [1, 3, 3, 2, 2], [3, 3], [3, 3, 2], [3, 3, 2, 2], [2, 2]$ have a maximum value that appears at least $2$ times. There are $7$ such subarrays with a power value of $1$, so the power level of the array is $7$.

In the second example, there is no subarray where the maximum value appears at least $3$ times, so the power level of the array is $0$.