海上有 n 座岛屿，自北向南排成一条直线，其中第 i（1 \le i \le n）座岛屿在这条直线上的坐标为整数 x_i，且 x_1 \lt x_2 \lt \cdots \lt x_n。每年秋季，一群海鸟会沿着这条直线在南北方向上迁徙，小 P 正在观察它们。

海鸟的体力有限，每次飞行的距离都不超过 d。若两座岛屿 i, j 满足 |x_i - x_j| \le d，海鸟就可以从第 i 座岛屿直接飞到第 j 座岛屿。

对于两座不同的岛屿 u, v，一条从第 u 座岛屿到第 v 座岛屿的路径形如 y_1 \to y_2 \to \cdots \to y_m，其中 y_1 = u，y_m = v，且对于所有 l（1 \le l \le m - 1），海鸟都能够从第 y_l 座岛屿直接飞到第 y_{l+1} 座岛屿；其长度为 m - 1，即海鸟在路径中飞行的次数。

小 P 发现，海鸟在迁徙时总是会选择长度最短的路径。对于两座岛屿 u, v（1 \le u \lt v \le n），若从第 u 座岛屿到第 v 座岛屿的长度最短的路径恰好有两条，海鸟可以分成两群，分别沿其中一条飞往第 v 座岛屿；此时称 (u, v) 为双径岛屿对。两条路径不同，当且仅当它们经过的岛屿序列不完全相同。

你需要帮助小 P 求出双径岛屿对的数量。

本题包含多组测试数据。

输入的第一行包含两个非负整数 c, t，分别表示测试点编号与测试数据组数。特别地，若 c = 0，则该测试点为样例。

接下来依次输入 t 组测试数据。对于每组测试数据：

• 第一行包含两个正整数 n, d，分别表示岛屿数量和海鸟一次最多能飞行的距离。

• 第二行包含 n 个严格递增的整数 x_1, x_2, \ldots, x_n，依次表示每座岛屿的坐标。

对于每组测试数据，输出一行一个非负整数，表示双径岛屿对的数量。

样例 1 解释：第一组数据仅有 1 个双径岛屿对 (1, 4)，两条最短路径为 1 \to 2 \to 4 和 1 \to 3 \to 4。第二组数据有 2 个双径岛屿对 (1, 4)、(2, 5)；从第 1 座到第 5 座只有一条最短路径 1 \to 3 \to 5，所以 (1, 5) 不是双径岛屿对。

样例 2 解释：第一组数据答案为 0，因为从第 1 座到第 5 座有三条最短路径 1 \to 2 \to 5、1 \to 3 \to 5、1 \to 4 \to 5。第二组数据仅有 1 个双径岛屿对 (1, 4)，第 5、6 座岛屿无法到达任何其他岛屿。

数据范围：设 N 为单个测试点内所有测试数据的 n 的和。对于所有测试数据，均有：

• 0 \le c \le 25，2 \le t \le 10^5；

• 1 \le n \le 2 \times 10^6，N \le 2 \times 10^6，1 \le d \le 2 \times 10^{18}；

• -10^{18} \le x_1 \lt x_2 \lt \cdots \lt x_n \le 10^{18}。

本题共 25 个等分测试点，每点 4 分。

特殊性质 A：每组数据中的 x_1, x_2, \ldots, x_n 构成等差数列。

特殊性质 B：每组数据中均存在一座岛屿，使得海鸟可以从它直接飞到任意其他岛屿。

特殊性质 C：每组数据均满足 x_n - x_1 \le 10d。

附加样例：官方题面另有样例 3 ~ 6 共四组大样例（分别满足测试点 3~6、11,12、15~18、19~21 的约束），因数据量较大未在此列出。

提示

岛屿在一条直线上且坐标严格递增，所以「能一步飞到」的岛屿恰好是一段连续区间：用双指针求出每个 i 能到达的最右岛屿 r_i（r_i 关于 i 单调不减），这一步就是 O(n)。

从 u 出发到右边任意一座岛屿，最短步数由「每步都尽量往右飞」的贪心分层唯一确定；而能够出现在某条最短路径第 l 步上的岛屿恰好排成一个连续段。因此最短路径的条数完全由各层的「衔接位置」决定：只有当某一层恰好比前后层多出一个可选岛屿、其余各层都唯一时，才会恰好产生两条最短路径。

把每个右端点 v 按它所属的层归类，对每个左端点 u 用递推统计「最短路条数恰为 2」的 v 的个数即可。所有 u 的统计量均摊是线性的，注意答案本身是 O(n^2) 量级，要用 64 位整数。