# Substring Counting

Time Limit: 2 Seconds

Memory Limit: 65536 KB

## Description

A non-empty string S is called binary, if it consists only of characters "0" and "1". A substring S[l...r] (1 ≤ l ≤ r ≤ |S|) of string S = S1S2...S|S| (where |S| is the length of string S) is string SlSl + 1...Sr.

Peter has got a long binary string S starting with "0", and he wants to know the number of distinct non-empty substrings of the string S that the occurrences of "0" in the substring is exact M, where M is Peter's lucky number. Two substrings S[x...y] and S[p...q] are considered distinct if their content is different, i.e. S[x...y] ≠ S[p...q].

Since the binary string is very long, we will compress it. The compression method is:

• Split the string to runs of same characters. Any two adjacent runs consist of different characters.
• Use the length of each run to represent the string.

For example, the runs of a binary string 00101100011110111101001111111 is {00, 1, 0, 11, 000, 1111, 0, 1111, 0, 1, 00, 1111111}, so it will be compressed into {2, 1, 1, 2, 3, 4, 1, 4, 1, 1, 2, 7}.

## Input

There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:

The first line contains two integers N and M (2 ≤ N ≤ 2000, 0 ≤ M ≤ 109) - the number of runs and Peter's lucky number.

The next line contains N integers: A1, A2, ..., AN (1 ≤ Ai ≤ 106), indicating the length of the each run.

## Output

For each test case, output an integer denoting the answer.

## Sample Input

1
3 2
3 2 1


## Sample Output

4


## Hint

The original binary string is 000110, the four substrings are: 00, 001, 0011, 0110.

None