令 $f(x)$ 表示 $x$ 的二进制表示中 $1$ 的个数。
现在 MianKing 有一个序列 $a_{0 \dots m-1}$，他想知道有多少个整数 $x \in [0, L]$ 满足：$\forall i \in [0, m - 1], f(x + i) \pmod 2 = a_i$。
你需要帮他计算出答案。
输入格式
本题包含 $T$ 组测试数据。 第一行包含一个整数 $T$。 对于每组测试数据，第一行包含两个整数 $m, L$。第二行包含 $m$ 个整数，表示 $a_{0 \dots m-1}$。
$1 \le T \le 1000$ $1 \le m \le 100$ $0 \le L \le 10^{18}$ $a_i \in \{0, 1\}$
输出格式
对于每组测试数据，输出一行答案。
样例
输入 1
3 3 10 0 1 0 1 1000 0 9 1000000 1 0 1 1 0 1 0 0 1
输出 1
2 501 41667