题目描述

海上有 $n$ 座岛屿，自北向南排成一条直线，其中第 $i\ (1 \le i \le n)$ 座岛屿在这条直线上的坐标为整数 $x_i$，且 $x_1 < x_2 < \cdots < 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 < 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

0 2
4 2
1 2 3 4
5 2
1 2 3 4 5

1
2

样例 2

0 2
5 3
-2 -1 0 1 2
6 2
-4 -3 -2 -1 3 6

0
1

说明

样例 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 解释：第一组中从 1 到 5 有三条最短路径 $1 \to 2 \to 5$、$1 \to 3 \to 5$、$1 \to 4 \to 5$，所以 $(1, 5)$ 不是双径岛屿对，答案为 0。第二组仅有 $(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 < x_2 < \cdots < x_n \le 10^{18}$。

• 特殊性质 A：$x_1, x_2, \ldots, x_n$ 构成等差数列。
• 特殊性质 B：存在一座岛屿，使得海鸟可以从该岛屿直接飞到任意其他岛屿。
• 特殊性质 C：$x_n - x_1 \le 10d$。

本题需要文件读写：输入文件 migrate.in，输出文件 migrate.out。

来源：CSP-S 2026 第二轮 T3。本 OJ 的测试数据为按题面测试点表自造，不是官方数据。本 OJ 内存上限为 512 MiB（原题 1024 MiB）。