Problem Description

Rounddog always has an array $a_1, a_2, \cdots, a_n$ in his right pocket, satisfying $1 \le a_i \le n$.

A subarray is a non-empty subsegment of the original array. Rounddog defines a good subarray as a subsegment $a_l, a_{l+1}, \cdots, a_r$ that all elements in it are different and $\max({a_l, a_{l+1}, \ldots, a_r}) - (r - l + 1) \leq k$.

Rounddog is not happy today. As his best friend, you want to find all good subarrays of $a$ to make him happy. In this case, please calculate the total number of good subarrays of $a$.

Input

The input contains several test cases, and the first line contains a single integer $T~(1 \leq T \leq 20)$, the number of test cases.

The first line of each test case contains two integers $n~(1\leq n \le 300\,000)$ and $k~(1\leq k \le 300\,000)$.

The second line contains $n$ integers, the $i$-th of which is $a_i~(1 \le a_i \le n)$.

It is guaranteed that the sum of $n$ over all test cases never exceeds $1\,000\,000$.

Output

One integer for each test case, representing the number of subarrays Rounddog likes.

2
5 3
2 3 2 2 5
10 4
1 5 4 3 6 2 10 8 4 5

7
31