题目描述

阿尔扎诺帝国魔术学院中，格伦老师难得认真地研究起了一本古老的禁忌教典。教典中记载了一种特殊的法术序列。序列由 $n$ 道咒文组成，第 $i$ 道咒文的魔力值为 $a_i$。

一开始，希丝缇娜以为只要把所有咒文的魔力简单相加，就能得到整个法术的强度。但格伦老师很快发现，这种咒文并不是这样运作的。第一道咒文会正向释放魔力，第二道咒文会反向抵消魔力，第三道咒文又会正向释放魔力，第四道咒文再次反向抵消魔力，之后依次交替。形式化地，对于一个法术序列 $b_1,b_2,...,b_m$，定义它的能量值为 $E(b)=\sum_{i=1}^{m}(-1)^{i+1}b_i$。空序列的能量值定义为 $0$。

在继续解析教典时，露米娅发现其中有一段连续咒文受到了异常魔力污染。如果直接吟唱，整个法术很可能会失控。于是格伦老师决定：必须恰好选择一段非空连续咒文，将它们从序列中抹去。也就是说，需要选择一个区间 $[l,r]$，删除 $a_l,a_{l+1},...,a_r$。被删除的咒文消失后，剩余咒文会按照原来的相对顺序自动连接成一个新的法术序列 $a_1,...,a_{l-1},a_{r+1},...,a_n$。

格伦老师希望最终得到的法术序列能量值恰好等于 $k$。请你帮助希丝缇娜和露米娅计算，有多少种不同的删除区间 $[l,r]$ 可以满足这个要求。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10^5$)，表示测试数据组数。

对于每组测试数据，第一行包含两个整数 $n,k$ ($1 \le n \le 10^6$，$-10^9 \le k \le 10^9$)，表示咒文数量和目标能量值。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$ ($-10^9 \le a_i \le 10^9$)，表示每道咒文的魔力值。

保证所有测试数据的 $n$ 之和不超过 $10^6$。

输出格式

对于每组测试数据，输出一个整数，表示满足要求的删除区间数量。

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

2
2
3