Given an integer sequence $a$ of length $n$ and an integer $k$, where the indices of $a$ are 1-based.

Let the $t$-th cyclic shift ($0 \le t < n$) of $a$ be the sequence $b$, where:

$$ b_i = a_{((i+t-1)\bmod n)+1} $$

Define the prefix sums of $b$ as:

$$ s_i = \sum_{j=1}^{i} b_j $$

Find the number of cyclic shifts $t$ such that there exists an $i \in [1,n]$ where $s_i = k$.

Input

The input contains multiple test cases.

The first line contains two non-negative integers $c$ and $t$, representing the subtask ID and the number of test cases, respectively. The sample case satisfies $c = 0$.

Each test case is provided as follows:

• The first line contains two positive integers $n$ and $k$, representing the length of the sequence and the target integer.
• The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ representing the sequence.

Output

For each test case, output a single non-negative integer representing your answer.

Examples

Input 1

0 10
2 4
2 2
4 2
1 1 -1 -1
1 0
1
2 -1
-2 -1
3 0
-2 -1 3
4 -2
1 -3 -2 -1
5 -3
-4 0 -5 1 5
6 -4
5 2 -1 3 -6 -3
7 -7
2 7 -5 -2 7 -1 -5
8 -3
-3 5 -5 4 -7 2 -2 -7

Output 1

2
1
0
1
3
2
5
2
1
3

Note

For the first test case, the sequence $a$ can only form $2, 2$ after cyclic shifts. Its prefix sum sequence contains the number $4$, so there are $2$ cyclic shifts whose prefix sum sequences contain the number $4$.

For the second test case, the sequence $a$ can form the following after cyclic shifts:

• $1, 1, -1, -1$, whose prefix sum sequence contains the number $2$.
• $-1, 1, 1, -1$, whose prefix sum sequence does not contain the number $2$.
• $-1, -1, 1, 1$, whose prefix sum sequence does not contain the number $2$.
• $1, -1, -1, 1$, whose prefix sum sequence does not contain the number $2$.

Thus, there is only $1$ cyclic shift scheme whose prefix sum sequence contains the number $2$.

Constraints

This problem uses bundled testing. The special constraints for each subtask are as follows:

• Subtask 1 (20 points): $\sum n \leq 2000$;
• Subtask 2 (15 points): $\sum n \leq 2 \times 10^5$, $a_i \ge 0$;
• Subtask 3 (15 points): $\sum n \leq 2 \times 10^5, k=0$;
• Subtask 4 (15 points): $\sum n \leq 2 \times 10^5$, $|a_i| \leq 1$;
• Subtask 5 (15 points): $\sum n \leq 2 \times 10^5$, for any $1 \le i \le n-2$, $a_i = a_{i+2}$ holds;
• Subtask 6 (10 points): $\sum n \leq 2 \times 10^5$;
• Subtask 7 (10 points): No special properties.

For all data, $1 \le t \le 10^6$, $1 \le n, \sum n \le 10^6$, $-10^9 \le a_i \le 10^9$, and $-10^{15} \le k \le 10^{15}$.