Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3942
Substring Counting

Time Limit: 2 Seconds      Memory Limit: 65536 KB

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.


Author: LIN, Xi
Source: The 13th Zhejiang Provincial Collegiate Programming Contest
Submit    Status