Binary Polynomials

A Boolean function of n variables is given by its algebraic normal form over arithmetic modulo 2. Coefficient a_j corresponds to the monomial containing exactly the variables selected by the set bits of j: a_0 is the constant, a_1x_1, a_2x_2, a_3x_2x_1, and so on through a_{2^n-1}x_n\cdots x_1.

For a given k, count the binary vectors with exactly k ones for which the function evaluates to 1.

Input

The first line contains the number of test cases T. Each following line contains n, k, and a binary string of exactly 2^n coefficients in the order above, where 1 \le n \le 18 and 0 \le k \le n.

Output

For each test case, print the required count.

Example

Input:

3
2 1 0111
4 2 1000000000000000
5 3 00000000000000000000000000000001

Output:

2
6
0