Each mapping \textbf{f} of the set \textbf{\{0,1\}^n} of \textbf{n}-dimensional binary vectors to \textbf{\{0,1\}} is called Boolean function of \textbf{n} variables and denoted by \textbf{f(x_n,x_\{n-1\},...,x_1)}. For cryptography some properties of the Boolean functions are interesting. Let denote by \textbf{B(n,k)} the set of \textbf{n}-dimensional binary vectors that have \textbf{k} \textbf{1}'s. The task is for given Boolean function \textbf{f} to find the number of vectors \textbf{(b_n,b_\{n-1\},...,b_1)} from \textbf{B(n,k)} such that \textbf{f(b_n,b_\{n-1\},...,b_1)=1}. The Boolean function will be given by its (unique) polynomial \textbf{modulo 2}. In these polynomials the operations addition and multiplication \textbf{modulo 2} are used, defined as shown in the tables of \textit{\textbf{Fig. 1}}. In the polynomial of a function any product of m variables \textbf{x_i1 x_i2 ... x_im} could participate or not participate. So the general form of the polynomial for \textbf{n}variables is: \textbf{a_0+a_1x_1+a_2x_2+a_3x_2x_1+a_4x_3+a_5x_3x_1+a_6x_3x_2+a_7x_3x_2x_1+. . .+a_nx_nx_\{n-1...\}x_1} where all coefficients \textbf{a_j}, \textbf{j=0,1,...,N=2^n-1}, are \textbf{0}'s or \textbf{1}'s and if the coefficient is equal to \textbf{0} we will omit the corresponding product and if it is equal to \textbf{1} we just will omit the coefficient. For example, the polynomial of the Boolean function disjunction of \textbf{2} variables given on \textit{\textbf{Fig. 2}} is \textbf{0+1.x_1+1.x_2+1.x_2x_1=x_1+x_2+x_2x_1}. \includegraphics{https://static.e-olymp.com/content/50/504e76c99ef9204a9976e93e9d14386a5747ee7e.jpg} \InputFile Your program has to be ready to solve more than one test case. The first line of the input file will contains only the number \textbf{T} of the test cases. Each of the following \textbf{T} lines will describe one function - first the numbers \textbf{n} and \textbf{k} separated by single space (\textbf{1} ≤ \textbf{n} ≤ \textbf{18}, \textbf{0} ≤ \textbf{k} ≤ \textbf{n}) and then, separated by one more space a string of \textbf{2^n} \textbf{0}'s and \textbf{1}'s that are the coefficients of the corresponding polynomial, ordered as in the general form of the polynomial given above. \OutputFile The output file have to contain \textbf{T} lines with a single number each - the number of vectors found by your program.