Rounddog 的右口袋里总是有一个数组 $a_1, a_2, \dots, a_n$，满足 $1 \le a_i \le n$。

子数组是原数组的一个非空子段。Rounddog 将子数组 $a_l, a_{l+1}, \dots, a_r$ 定义为“好”子数组，当且仅当其中的所有元素互不相同，且满足： $$\max(a_l, a_{l+1}, \dots, a_r) - (r - l + 1) \le k$$

Rounddog 今天很不开心。作为他最好的朋友，你想找出数组 $a$ 中所有的“好”子数组来让他开心。对于这个问题，请计算数组 $a$ 中“好”子数组的总数。

输入格式

输入包含多个测试用例。第一行包含一个整数 $T$ ($1 \le T \le 20$)，表示测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ ($1 \le n \le 300\,000$) 和 $k$ ($1 \le k \le 300\,000$)。 第二行包含 $n$ 个整数，其中第 $i$ 个数为 $a_i$ ($1 \le a_i \le n$)。

保证所有测试用例的 $n$ 之和不超过 $1\,000\,000$。

输出格式

对于每个测试用例，输出一行，包含一个整数：给定数组中“好”子数组的数量。

样例

输入 1

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

输出 1

7
31