F. Good Subarrays
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You have an array $$$a$$$ of $$$n$$$ integers and an integer $$$k$$$.

An array is called good if the arithmetic mean of its elements is not less than $$$k$$$.

You can perform the following operation at most once:

  • choose any index $$$i (1 \le i \le n)$$$, and set $$$a_i := a_i + 1$$$.

Now your task is to determine the maximum number of good subarrays of the array $$$a$$$ that can be formed by performing the operation at most once.

Input

The first line of input contains an integer $$$t$$$ $$$(1 \le t \le 10^5)$$$ — the number of testcases.

The first line of each testcase contains two integers $$$n$$$ $$$(1 \le n \le 2\cdot10^5)$$$ and $$$k$$$ $$$(1 \le k \le 10^9)$$$.

The second line of each testcase contains $$$n$$$ integers $$$a_1,a_2,a_3,...,a_n$$$ $$$(1 \le a_i \le 10^9)$$$.

It is guaranteed that the sum of $$$n$$$ over all testcases does not exceed $$$2\cdot10^5$$$.

Output

For each testcase, print the maximum number of good subarrays of the array $$$a$$$ that can be formed by performing the operation atmost once.

Example
Input
3
5 3
2 1 1 4 1
8 54
7 11 53 56 99 28 75 84
10 21
73 60 27 67 3 76 52 66 39 27
Output
3
21
54
Note

In the first test case, we can choose $$$i = 4$$$ and make $$$a_4 = a_4 + 1$$$.

After this operation, the array $$$a$$$ becomes $$$[2,1,1,5,1]$$$. Now we have $$$3$$$ subarrays $$$[5],[1,5]$$$ and $$$[5,1]$$$ with an average not less than $$$3$$$.