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` = `S`_{1}`S`_{2}...`S`_{|S|} (where |`S`| is the length of string `S`) is string
`S`_{l}`S`_{l + 1}...`S`_{r}.

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}.

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` ≤ 10^{9}) - the number of runs and Peter's lucky number.

The next line contains `N` integers: `A _{1}`,

提交代码