题目描述

海上有 $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_\ell$，其中 $y_1=u$，$y_\ell=v$，且相邻岛屿间可以直接飞行。路径的长度为 $\ell-1$，即海鸟在路径中飞行的次数。

对于两座岛屿 $u,v$（$1\le u<v\le n$），若从第 $u$ 座岛屿到第 $v$ 座岛屿的最短路径恰好有两条，则称 $(u,v)$ 为双径岛屿对。两条路径不同，当且仅当它们经过的岛屿序列不完全相同。

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

输入格式

本题包含多组测试数据。

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

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

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

输出格式

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

样例

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

1
2

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

0
1

数据范围

设 $N$ 为单个测试点内所有测试数据的 $n$ 的和。对于所有测试数据，$0\le c\le25$，$2\le t\le10^5$，$1\le n\le2\times10^6$，$N\le2\times10^6$，$1\le d\le2\times10^{18}$，$-10^{18}\le x_1<x_2<\cdots<x_n\le10^{18}$。

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

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

特殊性质 C：$x_n-x_1\le10d$。