#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <math.h>
#include <limits.h>
#include <assert.h>

#include <algorithm>

char a[1 << 18 + 1];
char f[1 << 18];

void compute_f_helper(int l, int i, char *result) {
    char *tmp = (char *) malloc((l / 2) * sizeof(*tmp));
    
    if (l == 1) {
        *result = (a[i] == '1');
        return;
    }
    
    compute_f_helper(l / 2, i, result);
    
    memcpy(result + l / 2, result, (l / 2) * sizeof(*tmp));
    
    compute_f_helper(l / 2, i + l / 2, tmp);
    
    for (int j = 0; j < l / 2; j++) {
        result[l / 2 + j] ^= tmp[j];
    }
    
    free(tmp);
}

void compute_f(int l) {
    char *tmp = (char *)malloc((l / 2) * sizeof(*tmp));
    
    compute_f_helper(l / 2, 0, f);

    memcpy(f + l / 2, f, (l / 2) * sizeof(*tmp));
    
    compute_f_helper(l / 2, l / 2, tmp);
    
    for (int i = 0; i < l / 2; i++) {
        f[l / 2 + i] ^= tmp[i];
    }
    
    free(tmp);
}

int count_result(int n, int k, int mask = 0) {
    if (n < k - 1)
        return 0;
    if (k == 0) {
        return f[mask];
    }
    
    return count_result(n - 1, k, mask) + count_result(n - 1, k - 1, mask | (1 << n));
}

int main (int argc, char **argv)
{
    int N;
    scanf("%d", &N);
    
    int n;
    int k;
    for (int i = 0; i < N; i++) {
        scanf("%d", &n);
        scanf("%d", &k);

        if (n == 0) {
            printf("0\n");
            continue;
        }

        for (int j = 0; j < (1 << n); j++) {
            scanf(" %c", &(a[j]));
        }
        //scanf("%s", a);
        
        compute_f(1 << n);
        
        printf("%d\n", count_result(n, k));
    }
    
    return 0;
}