D. Smartass (Smartass Version) - Light Pink
time limit per test
2 s
memory limit per test
256 megabytes
input
standard input
output
standard output

Rund just came back from her internship in Dublin where a falafel sandwich and a cup of tea costs a kidney for some reason. She also got scammed for the same amount for a mango back in Egypt. Oh and back in Jordan Aboud and Fakher are still playing 2v2v2v2. I'm so unbelievably bad at making stories so here's the problem.

This is the smartass version of the problem. Note that it differs slightly from the other versions

You are given an array $$$a$$$ of length $$$n$$$ consisting of integers

A subarray $$$a_l,a_{l+1},…,a_r$$$ is good if it isn't empty and the difference between the minimum and maximum element of this subarray is at most $$$k$$$ $$$(max(a_l,a_{l+1},…,a_r) - min(a_l,a_{l+1},…,a_r) ≤ k)$$$

Calculate the number of good subarrays in the array $$$a$$$

Input

The input consists of multiple test cases. The first line contains a single integer $$$t$$$ $$$(1≤t≤10^5)$$$ — the number of test cases

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ $$$(1≤n≤10^5, 0≤k≤10^9)$$$ — the length of the array and the maximum difference respectively

The second line of each test case consists of $$$n$$$ integers $$$a_1,a_2,…,a_n$$$ $$$(-10^9≤a_i≤10^9)$$$ — the elements of the array $$$a$$$

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$

Output

Print $$$t$$$ lines, each line containing the answer to the corresponding test case — the number of good subarrays in the array $$$a$$$

Example
Input
4
1 10
0
3 1
1 -1 0
5 2
1 2 3 4 5
10 5
1 2 3 -3 0 -2 -1 0 0 3
Output
1
4
12
33