points

Problem Statement :

Adam like points a lot. Adam’s father presented him with n points lying on the horizontal axis X on his birthday. Adam is a noob. So he needs your help to find in how many ways he can choose a set of three distinct points so that the distance between the two farthest of them does not exceed k.

Note that the order of the points inside the set of three distinct chosen points does not matter.

Input:

The first line of input contains T – No of test cases.(1 ≤ T ≤ 25)

Next T lines contains two integers: n and k (1 ≤ n ≤ 10^4;1 ≤ k ≤ 10^9). The next line contains n integers x1,x2,...,xn, and for each i in n (| xi | ≤ 10^9 )— the x-coordinates of the points that Adam has got.
The points x1,x2,...,xn  are strictly in increasing order. 

Output:

In T lines Print a single integer — the number of sets of three distinct points, where the distance between two farthest points doesn't exceed k.

Note: For C++ use cin, cout streams and for C use the %I64d specifier instead of %lld in printf() and scanf().

Explanation:

In the first sample test case any set of three points meets our conditions.

In the second sample test case only 2 sets of three points meet our conditions: {-3, -2, -1} and {-2, -1, 0}.

And in the last test case only one set does: {1, 10, 20}.

SAMPLE INPUT
3
4 3
1 2 3 4
4 2
-3 -2 -1 0
5 19
1 10 20 30 50

SAMPLE OUTPUT
4
2
1

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY
Tags: Sorting


Solutions: