Bit Sequence

题号：NC216187
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Let $f(x)$ denote the number of 1s in the binary representation of $x$ .

Now MianKing has a sequence $a_{0...m-1}$ and he wants to know the number of integer $x \in [0,L]$ satisfies that: $\forall i\in [0,m-1], f(x+i)~mod~2=a_i$

You need to help him calculate the answer.

输入描述:

There are  testcases in this problem.

The first line has one integer .

Then for each testcase, the first line has two integer . The second line has  integers denote

输出描述:

For each testcase, output the answer in one line.

示例1

输入

复制

3
3 10
0 1 0
1 1000
0
9 1000000
1 0 1 1 0 1 0 0 1

输出

复制

2
501
41667