D. Maximum Subarray Sum
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Given an array $$$A$$$ of length $$$N$$$, and a positive integer $$$K$$$.

Consider the following procedure to determine whether a subarray$$$^\dagger$$$ $$$A[L \dots R]$$$ is considered good or not:

  • Let's create a copy of this subarray, let's call it $$$C$$$ of length $$$R - L + 1$$$.
  • Let's define $$$S$$$ as the maximum subarray sum$$$^\ddagger$$$ in $$$C$$$.
  • If $$$S = K$$$, then the subarray $$$A[L \dots R]$$$ is good; otherwise, it is not good.

Your task is to count the number of good subarrays in $$$A$$$.

$$$\dagger$$$ A subarray is obtained by deleting several (possibly zero) elements from the start of the array and several (possibly zero) elements from the end of the array.

$$$\ddagger$$$ The maximum subarray sum in an array $$$B$$$ of length $$$M$$$ is equal to the maximum value of $$$B_L + B_{L + 1} + ... + B_R$$$ over all pairs of integers $$$L$$$, $$$R$$$ such that $$$1 \le L \le R \le M$$$.

Input

The first line of the input contains a single integer $$$T$$$ ($$$1 \le T \le 10$$$) — the number of testcases.

The first line of each testcase contains two space-separated integers $$$N$$$ and $$$K$$$ ($$$1 \le N \le 10^5, 1 \le K \le 10^{9}$$$) — the size of the array and the required maximum subarray sum.

The second line of each testcase contains $$$N$$$ space-separated integers $$$A_1, A_2, \dots, A_N$$$ ($$$-10^5 \le A_i \le 10^5$$$).

It's guaranteed that the sum of $$$N$$$ over all testcases doesn't exceed $$$10^5$$$.

Output

Output $$$T$$$ lines, each line containing a single integer — the answer for the corresponding testcase.

Example
Input
3
3 1
2 1 2
3 1
1 -2 1
4 2
1 2 -3 4
Output
1
5
2