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

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

对于两座不同的岛屿 u,v（1 \le u,v \le n），一条从第 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 < v \le n），若从第 u 座岛屿到第 v 座岛屿的长度最短的路径恰好有两条，海鸟可以分成两群，分别沿其中一条飞往第 v 座岛屿；此时称 (u,v) 为双径岛屿对。两条路径不同，当且仅当它们经过的岛屿序列不完全相同。

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

从文件 migrate.in 中读入数据。

本题包含多组测试数据。

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

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

• 第一行包含两个正整数 n,d，分别表示岛屿数量和海鸟一次最多能飞行的距离。
• 第二行包含 n 个严格递增的整数 x_1,x_2,\ldots,x_n，依次表示每座岛屿的坐标。

输出到文件 migrate.out 中。

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

样例 1 解释

该样例共包含两组测试数据。

对于第一组测试数据，仅有 1 个双径岛屿对 (1,4)。从第 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,5) 不是双径岛屿对。

对于第二组测试数据，仅有 1 个双径岛屿对 (1,4)。从第 1 座岛屿到第 4 座岛屿有两条长度最短的路径，分别为 1 \to 2 \to 4 和 1 \to 3 \to 4。第 5 座和第 6 座岛屿均无法到达任何其他岛屿。

样例 3

见题目目录下的 migrate/3.in 与 migrate/3.ans。

该样例满足测试点 3 \sim 6 的约束条件。

样例 4

见题目目录下的 migrate/4.in 与 migrate/4.ans。

该样例满足测试点 11,12 的约束条件。

样例 5

见题目目录下的 migrate/5.in 与 migrate/5.ans。

该样例满足测试点 15 \sim 18 的约束条件。

样例 6

见题目目录下的 migrate/6.in 与 migrate/6.ans。

该样例满足测试点 19 \sim 21 的约束条件。

数据范围

设 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 < x_2 < \cdots < x_n \le 10^{18}。

特殊性质 A：x_1,x_2,\ldots,x_n 构成等差数列。

特殊性质 B：存在一座岛屿，使得海鸟可以从该岛屿直接飞到任意其他岛屿。

特殊性质 C：x_n-x_1 \le 10d。

CSP-S 2026