Music

Interview

Time limit1sMemory limit128 MB

Summary

Count length-m windows whose max minus min is at most c, across several small arrays.

Level: Easy3 of 10
Topics: Sliding window, Array
Solved: No attempts yet

Problem

Silence is useless. We want the world to be full of music. In computer music, the volume is represented as an integer array of length $n$ . A silence in music is defined by two parameters $c$ and $m$ . A silence occurs in any contiguous subarray of length $m$ in which the difference between the maximum element and the minimum element is at most $c$ .

For example, if the volume array is $[1, 3, 2, 7, 5, 4, 6, 6]$ with $m = 3$ and $c = 2$ , then silence occurs in the length-3 subarrays starting at indices 0, 4, and 5. Output the total number of silence intervals.

Input

The first line contains an integer, the number of data sets that follow. Each data set consists of two lines. The first line contains three integers $n$ , $m$ , and $c$ ( $n \le 20$ , $m \le 20$ , $c \le 1000$ ). The second line contains $n$ integers representing the volume array; each integer is at most $1000$ .

Output

For each data set, print the total number of silence intervals.

Examples3

Example 1

Input

3
8 3 2
1 3 2 7 5 4 6 6
4 2 1
1 2 3 4
4 5 900
1 1 1 1

Expected output

3
3
0

Example 2
Input
```
1
5 1 0
1 2 3 4 5
```
Expected output
```
5
```
Example 3
Input
```
1
5 5 10
1 2 3 4 5
```
Expected output
```
1
```