F. 好数对

每个测试用例的时间限制：3 秒 每个测试用例的内存限制：256 兆字节

给定一个由 $n$ 个整数组成的数组 $a$ 和一个整数 $k$。

如果存在下标序列 $i_1,i_2,\dots,i_m$ 满足以下条件，则数对 $(l,r)$ 是好数对：

1. $i_1=l$ 且 $i_m=r$；
2. 对于所有 $1 \le j < m$，都有 $i_j < i_{j+1}$；
3. 对于所有 $1 \le j < m$，都有 $|a_{i_j} - a_{i_{j+1}}| \le k$。

请统计满足 $1 \le l \le r \le n$ 的好数对 $(l,r)$ 的数量。

输入格式

每个测试文件包含多个测试用例。 第一行包含一个整数 $t$（$1 \le t \le 10^5$），表示测试用例的数量。 每个测试用例的第一行包含两个用空格分隔的整数 $n$ 和 $k$（$1 \le n \le 5 \cdot 10^5$；$0 \le k \le 10^5$），分别表示数组 $a$ 的长度和整数 $k$。 每个测试用例的第二行包含 $n$ 个用空格分隔的整数 $a_1,a_2,\dots,a_n$（$1 \le a_i \le 10^5$），表示数组 $a$。

保证所有测试用例的 $n$ 之和不超过 $5 \cdot 10^5$。

输出格式

对于每个测试用例，输出好数对的数量。

样例输入

4
3 0
1 1 1
4 2
4 8 6 8
6 4
7 2 5 8 3 8
20 23
110 57 98 14 20 1 60 82 108 37 82 73 8 46 38 35 106 115 58 112

样例输出

6
9
18
92

样例说明

第一个测试用例中的好数对为：$(1,1)$、$(1,2)$、$(1,3)$、$(2,2)$、$(2,3)$、$(3,3)$。

第二个测试用例中的好数对为：$(1,1)$、$(1,3)$、$(1,4)$、$(2,2)$、$(2,3)$、$(2,4)$、$(3,3)$、$(3,4)$、$(4,4)$。 数对 $(1,4)$ 是好数对，因为存在下标序列 $1,3,4$ 满足题目给定的条件。