H. Happiness Index
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The government is very concerned about the happiness index of residents. In the practical work of ideological and political courses, Master Yi collected the happiness index of $$$n$$$ residents in his hometown as an integer array $$$a_1, a_2, \cdots, a_n$$$.

In this task, Master Yi wants to know how many intervals are there satisfying that the average happiness index in this interval is approximately $$$k$$$. In other words, please help him calculate how many intervals $$$[l,r]$$$ satisfy $$$\lfloor{\frac{a_l+a_{l+1}+\cdots+a_r}{r-l+1}}\rfloor=k$$$.

Input

The first line contains a single integer $$$t\ (1\le t\le 10^4)$$$, the number of test cases. For each test case:

The first line contains $$$2$$$ integers $$$n\ (1\le n\le 2\cdot 10^5)$$$ and $$$k\ (0\le k\le 10^9)$$$, the number of the interviewed residents and the required happiness index.

The second line contains $$$n$$$ integers $$$a_1, a_2, \cdots, a_n\ (0\le a_i\le 10^9)$$$, which are the happiness indexes of each interviewed resident.

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

Output

For each test case, print the answer in a single line, which is the number of subsegments satisfying the condition.

Example
Input
1
3 2
2 1 3
Output
3
Note

In the first example, the subsegments satisfying the condition are $$$[2]$$$, $$$[1,3]$$$ and $$$[2,1,3]$$$, each has an average happiness index of $$$2$$$.