410482: GYM104025 H Happiness Index

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

H. Happiness Indextime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard 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.

ExampleInput
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$$$.

加入题单

上一题 下一题 算法标签: