#include <bits/stdc++.h>using i64 = long long;void Solve() { int n; i64 d; std::cin >> n >> d; std::vector<i64> x(n); for (int i = 0; i < n; i++) { std::cin >> x[i]; } std::vector<int> right(n, -1); for (int i = n - 1, j = n - 1; i >= 0; i--) { while (j > i && x[j] - x[i] > d) { j--; } right[i] = j; } std::vector<int> g(n, n); std::vector<int> left(n, n); for (int i = 0, j = 0; i < n; i++) { while (j < i && x[i] - x[j] > d) { j++; } g[j] = std::min(g[j], i); left[i] = j; } constexpr int A = 3, B = 3, V = 2; constexpr int STRIDE_A = B * V; // 6 constexpr int STRIDE_B = V; // 2 constexpr int STRIDE_I = A * B * V; // 18 std::vector<int> f(n * STRIDE_I); auto F = [&](int i, int a, int b, int v) -> int& { return f[i * STRIDE_I + (a - 1) * STRIDE_A + (b - 1) * STRIDE_B + (v - 1)]; }; for (int i = n - 1; i >= 1; i--) { if (right[i] == i) { continue; } int j = right[i]; if (j == i) { continue; } for (int a = 1; a <= 3; a++) { for (int b = 1; b <= 3; b++) { if (j == i + 1) { int c = std::min(3, left[j] == i ? b : left[j] == i - 1 ? a + b : 3); F(i, a, b, 1) += F(j, 1, c, 1); F(i, a, b, 2) += F(j, 1, c, 2); if (c <= 2) { F(i, a, b, c) += 1; } continue; } int p1 = std::max(i + 1, g[i - 1]), p2 = std::min(j + 1, g[i]); if (b <= 2) { F(i, a, b, b) += j - p2 + 1; } if (a + b <= 2) { F(i, a, b, a + b) += std::max(0, p2 - p1); } int c = std::min(3, left[j - 1] < i - 1 ? 3 : left[j - 1] == i - 1 ? a + b : b); int d = std::min(3, left[j] < i - 1 ? 3 : left[j] == i - 1 ? a + b : b); F(i, a, b, 1) += F(j, c, d, 1); F(i, a, b, 2) += F(j, c, d, 2); } } } i64 ans = 0, lst = 0; for (int i = n - 1; i >= 0; i--) { if (right[i] == i) { lst = 0; continue; } if (right[i] == i + 1) { ans += lst; continue; } lst = F(right[i], 1, 1, 2); ans += lst; // std::cout << lst << " "; } // std::cout << "\n"; std::cout << ans << '\n'; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); int c, t; std::cin >> c >> t; while (t --) { Solve(); } return 0;}