public static void main(String[] args) throws IOException {
        reader = new BufferedReader(new InputStreamReader(in));
        tokenizer = new StringTokenizer("");
        PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(out)));

        int T = nextInt();
        for (int t = 0; t < T; t++) {
            String s = next();
            int N = nextInt();
            boolean toggel;
            if (N == 0)
                toggel = false;
            else if (N % 2 != 0) {
                toggel = canToggel(N);
            } else {
                toggel = canToggel(N - 1);
            }

            int count = 0;
            if (toggel) {
                for (char c : s.toCharArray()) {
                    if (c == '0') {
                        count++;
                    }
                }
            } else {
                for (char c : s.toCharArray()) {
                    if (c == '1') {
                        count++;
                    }
                }
            }

            pw.println(count);
        }


        reader.close();
        pw.close();
    }