Problem Description

At the Alzano Empire Magic Academy, Teacher Glenn is seriously studying an ancient forbidden grimoire. The grimoire records a special sequence of spells. The sequence consists of $n$ spells, and the magic power of the $i$-th spell is $a_i$.

At first, Sistine thought that simply summing the magic power of all spells would give the strength of the whole spell. But Teacher Glenn soon found that these spells do not work that way. The first spell releases magic power positively, the second spell cancels magic power in reverse, the third spell releases magic power positively again, the fourth spell cancels it in reverse again, and so on alternately. Formally, for a spell sequence $b_1,b_2,\ldots,b_m$, define its energy value as $E(b)=\sum_{i=1}^{m}(-1)^{i+1}b_i$. The energy value of an empty sequence is defined as $0$.

While continuing to analyze the grimoire, Rumia发现 that a contiguous segment of spells has been polluted by abnormal magic. If chanted directly, the whole spell is very likely to go out of control. Therefore, Teacher Glenn decides that you must choose exactly one non-empty contiguous segment of spells and erase them from the sequence. That is, choose an interval $[l,r]$ and delete $a_l,a_{l+1},\ldots,a_r$. After the deleted spells disappear, the remaining spells will automatically connect in their original relative order to form a new spell sequence $a_1,\ldots,a_{l-1},a_{r+1},\ldots,a_n$.

Teacher Glenn hopes that the energy value of the final spell sequence is exactly $k$. Please help Sistine and Rumia compute how many different deletion intervals $[l,r]$ can satisfy this requirement.

Input Format

The first line contains an integer $t$ ($1 \le t \le 10^5$), indicating the number of testdata sets.

For each testdata set, the first line contains two integers $n,k$ ($1 \le n \le 10^6$，$-10^9 \le k \le 10^9$), indicating the number of spells and the target energy value.

The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($-10^9 \le a_i \le 10^9$), indicating the magic power of each spell.

It is guaranteed that the sum of $n$ over all testdata sets does not exceed $10^6$.

Output Format

For each testdata set, output one integer, the number of deletion intervals that satisfy the requirement.

3
4 0
1 3 2 4
3 0
1 2 1
5 1
2 1 3 4 2

2
2
3

Hint

Translated by ChatGPT 5